Back to home page

LXR

 
 

    


0001 /*
0002  *  Deadline i/o scheduler.
0003  *
0004  *  Copyright (C) 2002 Jens Axboe <axboe@kernel.dk>
0005  */
0006 #include <linux/kernel.h>
0007 #include <linux/fs.h>
0008 #include <linux/blkdev.h>
0009 #include <linux/elevator.h>
0010 #include <linux/bio.h>
0011 #include <linux/module.h>
0012 #include <linux/slab.h>
0013 #include <linux/init.h>
0014 #include <linux/compiler.h>
0015 #include <linux/rbtree.h>
0016 
0017 /*
0018  * See Documentation/block/deadline-iosched.txt
0019  */
0020 static const int read_expire = HZ / 2;  /* max time before a read is submitted. */
0021 static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
0022 static const int writes_starved = 2;    /* max times reads can starve a write */
0023 static const int fifo_batch = 16;       /* # of sequential requests treated as one
0024                      by the above parameters. For throughput. */
0025 
0026 struct deadline_data {
0027     /*
0028      * run time data
0029      */
0030 
0031     /*
0032      * requests (deadline_rq s) are present on both sort_list and fifo_list
0033      */
0034     struct rb_root sort_list[2];    
0035     struct list_head fifo_list[2];
0036 
0037     /*
0038      * next in sort order. read, write or both are NULL
0039      */
0040     struct request *next_rq[2];
0041     unsigned int batching;      /* number of sequential requests made */
0042     unsigned int starved;       /* times reads have starved writes */
0043 
0044     /*
0045      * settings that change how the i/o scheduler behaves
0046      */
0047     int fifo_expire[2];
0048     int fifo_batch;
0049     int writes_starved;
0050     int front_merges;
0051 };
0052 
0053 static void deadline_move_request(struct deadline_data *, struct request *);
0054 
0055 static inline struct rb_root *
0056 deadline_rb_root(struct deadline_data *dd, struct request *rq)
0057 {
0058     return &dd->sort_list[rq_data_dir(rq)];
0059 }
0060 
0061 /*
0062  * get the request after `rq' in sector-sorted order
0063  */
0064 static inline struct request *
0065 deadline_latter_request(struct request *rq)
0066 {
0067     struct rb_node *node = rb_next(&rq->rb_node);
0068 
0069     if (node)
0070         return rb_entry_rq(node);
0071 
0072     return NULL;
0073 }
0074 
0075 static void
0076 deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
0077 {
0078     struct rb_root *root = deadline_rb_root(dd, rq);
0079 
0080     elv_rb_add(root, rq);
0081 }
0082 
0083 static inline void
0084 deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
0085 {
0086     const int data_dir = rq_data_dir(rq);
0087 
0088     if (dd->next_rq[data_dir] == rq)
0089         dd->next_rq[data_dir] = deadline_latter_request(rq);
0090 
0091     elv_rb_del(deadline_rb_root(dd, rq), rq);
0092 }
0093 
0094 /*
0095  * add rq to rbtree and fifo
0096  */
0097 static void
0098 deadline_add_request(struct request_queue *q, struct request *rq)
0099 {
0100     struct deadline_data *dd = q->elevator->elevator_data;
0101     const int data_dir = rq_data_dir(rq);
0102 
0103     deadline_add_rq_rb(dd, rq);
0104 
0105     /*
0106      * set expire time and add to fifo list
0107      */
0108     rq->fifo_time = jiffies + dd->fifo_expire[data_dir];
0109     list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
0110 }
0111 
0112 /*
0113  * remove rq from rbtree and fifo.
0114  */
0115 static void deadline_remove_request(struct request_queue *q, struct request *rq)
0116 {
0117     struct deadline_data *dd = q->elevator->elevator_data;
0118 
0119     rq_fifo_clear(rq);
0120     deadline_del_rq_rb(dd, rq);
0121 }
0122 
0123 static int
0124 deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
0125 {
0126     struct deadline_data *dd = q->elevator->elevator_data;
0127     struct request *__rq;
0128     int ret;
0129 
0130     /*
0131      * check for front merge
0132      */
0133     if (dd->front_merges) {
0134         sector_t sector = bio_end_sector(bio);
0135 
0136         __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
0137         if (__rq) {
0138             BUG_ON(sector != blk_rq_pos(__rq));
0139 
0140             if (elv_bio_merge_ok(__rq, bio)) {
0141                 ret = ELEVATOR_FRONT_MERGE;
0142                 goto out;
0143             }
0144         }
0145     }
0146 
0147     return ELEVATOR_NO_MERGE;
0148 out:
0149     *req = __rq;
0150     return ret;
0151 }
0152 
0153 static void deadline_merged_request(struct request_queue *q,
0154                     struct request *req, int type)
0155 {
0156     struct deadline_data *dd = q->elevator->elevator_data;
0157 
0158     /*
0159      * if the merge was a front merge, we need to reposition request
0160      */
0161     if (type == ELEVATOR_FRONT_MERGE) {
0162         elv_rb_del(deadline_rb_root(dd, req), req);
0163         deadline_add_rq_rb(dd, req);
0164     }
0165 }
0166 
0167 static void
0168 deadline_merged_requests(struct request_queue *q, struct request *req,
0169              struct request *next)
0170 {
0171     /*
0172      * if next expires before rq, assign its expire time to rq
0173      * and move into next position (next will be deleted) in fifo
0174      */
0175     if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
0176         if (time_before((unsigned long)next->fifo_time,
0177                 (unsigned long)req->fifo_time)) {
0178             list_move(&req->queuelist, &next->queuelist);
0179             req->fifo_time = next->fifo_time;
0180         }
0181     }
0182 
0183     /*
0184      * kill knowledge of next, this one is a goner
0185      */
0186     deadline_remove_request(q, next);
0187 }
0188 
0189 /*
0190  * move request from sort list to dispatch queue.
0191  */
0192 static inline void
0193 deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
0194 {
0195     struct request_queue *q = rq->q;
0196 
0197     deadline_remove_request(q, rq);
0198     elv_dispatch_add_tail(q, rq);
0199 }
0200 
0201 /*
0202  * move an entry to dispatch queue
0203  */
0204 static void
0205 deadline_move_request(struct deadline_data *dd, struct request *rq)
0206 {
0207     const int data_dir = rq_data_dir(rq);
0208 
0209     dd->next_rq[READ] = NULL;
0210     dd->next_rq[WRITE] = NULL;
0211     dd->next_rq[data_dir] = deadline_latter_request(rq);
0212 
0213     /*
0214      * take it off the sort and fifo list, move
0215      * to dispatch queue
0216      */
0217     deadline_move_to_dispatch(dd, rq);
0218 }
0219 
0220 /*
0221  * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
0222  * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
0223  */
0224 static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
0225 {
0226     struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
0227 
0228     /*
0229      * rq is expired!
0230      */
0231     if (time_after_eq(jiffies, (unsigned long)rq->fifo_time))
0232         return 1;
0233 
0234     return 0;
0235 }
0236 
0237 /*
0238  * deadline_dispatch_requests selects the best request according to
0239  * read/write expire, fifo_batch, etc
0240  */
0241 static int deadline_dispatch_requests(struct request_queue *q, int force)
0242 {
0243     struct deadline_data *dd = q->elevator->elevator_data;
0244     const int reads = !list_empty(&dd->fifo_list[READ]);
0245     const int writes = !list_empty(&dd->fifo_list[WRITE]);
0246     struct request *rq;
0247     int data_dir;
0248 
0249     /*
0250      * batches are currently reads XOR writes
0251      */
0252     if (dd->next_rq[WRITE])
0253         rq = dd->next_rq[WRITE];
0254     else
0255         rq = dd->next_rq[READ];
0256 
0257     if (rq && dd->batching < dd->fifo_batch)
0258         /* we have a next request are still entitled to batch */
0259         goto dispatch_request;
0260 
0261     /*
0262      * at this point we are not running a batch. select the appropriate
0263      * data direction (read / write)
0264      */
0265 
0266     if (reads) {
0267         BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
0268 
0269         if (writes && (dd->starved++ >= dd->writes_starved))
0270             goto dispatch_writes;
0271 
0272         data_dir = READ;
0273 
0274         goto dispatch_find_request;
0275     }
0276 
0277     /*
0278      * there are either no reads or writes have been starved
0279      */
0280 
0281     if (writes) {
0282 dispatch_writes:
0283         BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
0284 
0285         dd->starved = 0;
0286 
0287         data_dir = WRITE;
0288 
0289         goto dispatch_find_request;
0290     }
0291 
0292     return 0;
0293 
0294 dispatch_find_request:
0295     /*
0296      * we are not running a batch, find best request for selected data_dir
0297      */
0298     if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
0299         /*
0300          * A deadline has expired, the last request was in the other
0301          * direction, or we have run out of higher-sectored requests.
0302          * Start again from the request with the earliest expiry time.
0303          */
0304         rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
0305     } else {
0306         /*
0307          * The last req was the same dir and we have a next request in
0308          * sort order. No expired requests so continue on from here.
0309          */
0310         rq = dd->next_rq[data_dir];
0311     }
0312 
0313     dd->batching = 0;
0314 
0315 dispatch_request:
0316     /*
0317      * rq is the selected appropriate request.
0318      */
0319     dd->batching++;
0320     deadline_move_request(dd, rq);
0321 
0322     return 1;
0323 }
0324 
0325 static void deadline_exit_queue(struct elevator_queue *e)
0326 {
0327     struct deadline_data *dd = e->elevator_data;
0328 
0329     BUG_ON(!list_empty(&dd->fifo_list[READ]));
0330     BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
0331 
0332     kfree(dd);
0333 }
0334 
0335 /*
0336  * initialize elevator private data (deadline_data).
0337  */
0338 static int deadline_init_queue(struct request_queue *q, struct elevator_type *e)
0339 {
0340     struct deadline_data *dd;
0341     struct elevator_queue *eq;
0342 
0343     eq = elevator_alloc(q, e);
0344     if (!eq)
0345         return -ENOMEM;
0346 
0347     dd = kzalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
0348     if (!dd) {
0349         kobject_put(&eq->kobj);
0350         return -ENOMEM;
0351     }
0352     eq->elevator_data = dd;
0353 
0354     INIT_LIST_HEAD(&dd->fifo_list[READ]);
0355     INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
0356     dd->sort_list[READ] = RB_ROOT;
0357     dd->sort_list[WRITE] = RB_ROOT;
0358     dd->fifo_expire[READ] = read_expire;
0359     dd->fifo_expire[WRITE] = write_expire;
0360     dd->writes_starved = writes_starved;
0361     dd->front_merges = 1;
0362     dd->fifo_batch = fifo_batch;
0363 
0364     spin_lock_irq(q->queue_lock);
0365     q->elevator = eq;
0366     spin_unlock_irq(q->queue_lock);
0367     return 0;
0368 }
0369 
0370 /*
0371  * sysfs parts below
0372  */
0373 
0374 static ssize_t
0375 deadline_var_show(int var, char *page)
0376 {
0377     return sprintf(page, "%d\n", var);
0378 }
0379 
0380 static ssize_t
0381 deadline_var_store(int *var, const char *page, size_t count)
0382 {
0383     char *p = (char *) page;
0384 
0385     *var = simple_strtol(p, &p, 10);
0386     return count;
0387 }
0388 
0389 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV)                \
0390 static ssize_t __FUNC(struct elevator_queue *e, char *page)     \
0391 {                                   \
0392     struct deadline_data *dd = e->elevator_data;            \
0393     int __data = __VAR;                     \
0394     if (__CONV)                         \
0395         __data = jiffies_to_msecs(__data);          \
0396     return deadline_var_show(__data, (page));           \
0397 }
0398 SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
0399 SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
0400 SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
0401 SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
0402 SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
0403 #undef SHOW_FUNCTION
0404 
0405 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)         \
0406 static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
0407 {                                   \
0408     struct deadline_data *dd = e->elevator_data;            \
0409     int __data;                         \
0410     int ret = deadline_var_store(&__data, (page), count);       \
0411     if (__data < (MIN))                     \
0412         __data = (MIN);                     \
0413     else if (__data > (MAX))                    \
0414         __data = (MAX);                     \
0415     if (__CONV)                         \
0416         *(__PTR) = msecs_to_jiffies(__data);            \
0417     else                                \
0418         *(__PTR) = __data;                  \
0419     return ret;                         \
0420 }
0421 STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
0422 STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
0423 STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
0424 STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
0425 STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
0426 #undef STORE_FUNCTION
0427 
0428 #define DD_ATTR(name) \
0429     __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
0430                       deadline_##name##_store)
0431 
0432 static struct elv_fs_entry deadline_attrs[] = {
0433     DD_ATTR(read_expire),
0434     DD_ATTR(write_expire),
0435     DD_ATTR(writes_starved),
0436     DD_ATTR(front_merges),
0437     DD_ATTR(fifo_batch),
0438     __ATTR_NULL
0439 };
0440 
0441 static struct elevator_type iosched_deadline = {
0442     .ops = {
0443         .elevator_merge_fn =        deadline_merge,
0444         .elevator_merged_fn =       deadline_merged_request,
0445         .elevator_merge_req_fn =    deadline_merged_requests,
0446         .elevator_dispatch_fn =     deadline_dispatch_requests,
0447         .elevator_add_req_fn =      deadline_add_request,
0448         .elevator_former_req_fn =   elv_rb_former_request,
0449         .elevator_latter_req_fn =   elv_rb_latter_request,
0450         .elevator_init_fn =     deadline_init_queue,
0451         .elevator_exit_fn =     deadline_exit_queue,
0452     },
0453 
0454     .elevator_attrs = deadline_attrs,
0455     .elevator_name = "deadline",
0456     .elevator_owner = THIS_MODULE,
0457 };
0458 
0459 static int __init deadline_init(void)
0460 {
0461     return elv_register(&iosched_deadline);
0462 }
0463 
0464 static void __exit deadline_exit(void)
0465 {
0466     elv_unregister(&iosched_deadline);
0467 }
0468 
0469 module_init(deadline_init);
0470 module_exit(deadline_exit);
0471 
0472 MODULE_AUTHOR("Jens Axboe");
0473 MODULE_LICENSE("GPL");
0474 MODULE_DESCRIPTION("deadline IO scheduler");