block/zen-iosched.c

   1 /*
   2  * Zen IO scheduler
   3  * Primarily based on Noop, deadline, and SIO IO schedulers.
   4  *
   5  * Copyright (C) 2012 Brandon Berhent <bbedward@gmail.com>
   6  *           (C) 2014 LoungeKatt <twistedumbrella@gmail.com>
   7  *           (c) 2015 Fixes to stop crashing on 3.10 by Matthew Alex <matthewalex@outlook.com>
   8  *           (c) 2016 POrt and fixes for Linux 3.18 by engstk <eng.stk@sapo.pt>
   9  *
  10  * FCFS, dispatches are back-inserted, deadlines ensure fairness.
  11  * Should work best with devices where there is no travel delay.
  12  */
  13 #include <linux/blkdev.h>
  14 #include <linux/elevator.h>
  15 #include <linux/bio.h>
  16 #include <linux/module.h>
  17 #include <linux/slab.h>
  18 #include <linux/init.h>
  19
  20 enum zen_data_dir { ASYNC, SYNC };
  21
  22 static const int sync_expire  = HZ / 2;    /* max time before a sync is submitted. */
  23 static const int async_expire = 5 * HZ;    /* ditto for async, these limits are SOFT! */
  24 static const int fifo_batch = 16;
  25
  26 struct zen_data {
  27         /* Runtime Data */
  28         /* Requests are only present on fifo_list */
  29         struct list_head fifo_list[2];
  30
  31         unsigned int batching;          /* number of sequential requests made */
  32
  33         /* tunables */
  34         int fifo_expire[2];
  35         int fifo_batch;
  36 };
  37
  38 static inline struct zen_data *
  39 zen_get_data(struct request_queue *q) {
  40         return q->elevator->elevator_data;
  41 }
  42
  43 static void zen_dispatch(struct zen_data *, struct request *);
  44
  45 static void
  46 zen_merged_requests(struct request_queue *q, struct request *req,
  47                     struct request *next)
  48 {
  49         /*
  50          * if next expires before rq, assign its expire time to arq
  51          * and move into next position (next will be deleted) in fifo
  52          */
  53         if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
  54                 if (time_before(next->fifo_time, req->fifo_time)) {
  55                         list_move(&req->queuelist, &next->queuelist);
  56                         req->fifo_time = next->fifo_time;
  57                 }
  58         }
  59
  60         /* next request is gone */
  61         rq_fifo_clear(next);
  62 }
  63
  64 static void zen_add_request(struct request_queue *q, struct request *rq)
  65 {
  66         struct zen_data *zdata = zen_get_data(q);
  67         const int sync = rq_is_sync(rq);
  68
  69         if (zdata->fifo_expire[sync]) {
  70                 rq->fifo_time = jiffies + zdata->fifo_expire[sync];
  71                 list_add_tail(&rq->queuelist, &zdata->fifo_list[sync]);
  72         }
  73 }
  74
  75 static void zen_dispatch(struct zen_data *zdata, struct request *rq)
  76 {
  77         /* Remove request from list and dispatch it */
  78         rq_fifo_clear(rq);
  79         elv_dispatch_add_tail(rq->q, rq);
  80
  81         /* Increment # of sequential requests */
  82         zdata->batching++;
  83 }
  84
  85 /*
  86  * get the first expired request in direction ddir
  87  */
  88 static struct request *
  89 zen_expired_request(struct zen_data *zdata, int ddir)
  90 {
  91         struct request *rq;
  92
  93         if (list_empty(&zdata->fifo_list[ddir]))
  94                 return NULL;
  95
  96         rq = rq_entry_fifo(zdata->fifo_list[ddir].next);
  97         if (time_after_eq(jiffies, rq->fifo_time))
  98                 return rq;
  99
 100         return NULL;
 101 }
 102
 103 /*
 104  * zen_check_fifo returns 0 if there are no expired requests on the fifo,
 105  * otherwise it returns the next expired request
 106  */
 107 static struct request *
 108 zen_check_fifo(struct zen_data *zdata)
 109 {
 110         struct request *rq_sync = zen_expired_request(zdata, SYNC);
 111         struct request *rq_async = zen_expired_request(zdata, ASYNC);
 112
 113         if (rq_async && rq_sync) {
 114                 if (time_after(rq_async->fifo_time, rq_sync->fifo_time))
 115                         return rq_sync;
 116         } else if (rq_sync) {
 117                 return rq_sync;
 118         } else if (rq_async) {
 119                 return rq_async;
 120         }
 121
 122         return 0;
 123 }
 124
 125 static struct request *
 126 zen_choose_request(struct zen_data *zdata)
 127 {
 128         /*
 129          * Retrieve request from available fifo list.
 130          * Synchronous requests have priority over asynchronous.
 131          */
 132         if (!list_empty(&zdata->fifo_list[SYNC]))
 133                 return rq_entry_fifo(zdata->fifo_list[SYNC].next);
 134         if (!list_empty(&zdata->fifo_list[ASYNC]))
 135                 return rq_entry_fifo(zdata->fifo_list[ASYNC].next);
 136
 137         return NULL;
 138 }
 139
 140 static int zen_dispatch_requests(struct request_queue *q, int force)
 141 {
 142         struct zen_data *zdata = zen_get_data(q);
 143         struct request *rq = NULL;
 144
 145         /* Check for and issue expired requests */
 146         if (zdata->batching > zdata->fifo_batch) {
 147                 zdata->batching = 0;
 148                 rq = zen_check_fifo(zdata);
 149         }
 150
 151         if (!rq) {
 152                 rq = zen_choose_request(zdata);
 153                 if (!rq)
 154                         return 0;
 155         }
 156
 157         zen_dispatch(zdata, rq);
 158
 159         return 1;
 160 }
 161
 162 static int zen_init_queue(struct request_queue *q, struct elevator_type *e)
 163 {
 164         struct zen_data *zdata;
 165     struct elevator_queue *eq;
 166
 167     eq = elevator_alloc(q, e);
 168     if (!eq)
 169         return -ENOMEM;
 170
 171     zdata = kmalloc_node(sizeof(*zdata), GFP_KERNEL, q->node);
 172     if (!zdata) {
 173         kobject_put(&eq->kobj);
 174         return -ENOMEM;
 175     }
 176     eq->elevator_data = zdata;
 177
 178
 179     spin_lock_irq(q->queue_lock);
 180         q->elevator = eq;
 181         spin_unlock_irq(q->queue_lock);
 182
 183         INIT_LIST_HEAD(&zdata->fifo_list[SYNC]);
 184         INIT_LIST_HEAD(&zdata->fifo_list[ASYNC]);
 185         zdata->fifo_expire[SYNC] = sync_expire;
 186         zdata->fifo_expire[ASYNC] = async_expire;
 187         zdata->fifo_batch = fifo_batch;
 188         return 0;
 189 }
 190
 191 static void zen_exit_queue(struct elevator_queue *e)
 192 {
 193         struct zen_data *zdata = e->elevator_data;
 194
 195         BUG_ON(!list_empty(&zdata->fifo_list[SYNC]));
 196         BUG_ON(!list_empty(&zdata->fifo_list[ASYNC]));
 197         kfree(zdata);
 198 }
 199
 200 /* Sysfs */
 201 static ssize_t
 202 zen_var_show(int var, char *page)
 203 {
 204         return sprintf(page, "%d\n", var);
 205 }
 206
 207 static ssize_t
 208 zen_var_store(int *var, const char *page, size_t count)
 209 {
 210         *var = simple_strtol(page, NULL, 10);
 211         return count;
 212 }
 213
 214 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
 215 static ssize_t __FUNC(struct elevator_queue *e, char *page) \
 216 { \
 217         struct zen_data *zdata = e->elevator_data; \
 218         int __data = __VAR; \
 219         if (__CONV) \
 220                 __data = jiffies_to_msecs(__data); \
 221                 return zen_var_show(__data, (page)); \
 222 }
 223 SHOW_FUNCTION(zen_sync_expire_show, zdata->fifo_expire[SYNC], 1);
 224 SHOW_FUNCTION(zen_async_expire_show, zdata->fifo_expire[ASYNC], 1);
 225 SHOW_FUNCTION(zen_fifo_batch_show, zdata->fifo_batch, 0);
 226 #undef SHOW_FUNCTION
 227
 228 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
 229 static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
 230 { \
 231         struct zen_data *zdata = e->elevator_data; \
 232         int __data; \
 233         int ret = zen_var_store(&__data, (page), count); \
 234         if (__data < (MIN)) \
 235                 __data = (MIN); \
 236         else if (__data > (MAX)) \
 237                 __data = (MAX); \
 238         if (__CONV) \
 239                 *(__PTR) = msecs_to_jiffies(__data); \
 240         else \
 241                 *(__PTR) = __data; \
 242         return ret; \
 243 }
 244 STORE_FUNCTION(zen_sync_expire_store, &zdata->fifo_expire[SYNC], 0, INT_MAX, 1);
 245 STORE_FUNCTION(zen_async_expire_store, &zdata->fifo_expire[ASYNC], 0, INT_MAX, 1);
 246 STORE_FUNCTION(zen_fifo_batch_store, &zdata->fifo_batch, 0, INT_MAX, 0);
 247 #undef STORE_FUNCTION
 248
 249 #define DD_ATTR(name) \
 250         __ATTR(name, S_IRUGO|S_IWUSR, zen_##name##_show, \
 251                                       zen_##name##_store)
 252
 253 static struct elv_fs_entry zen_attrs[] = {
 254         DD_ATTR(sync_expire),
 255         DD_ATTR(async_expire),
 256         DD_ATTR(fifo_batch),
 257         __ATTR_NULL
 258 };
 259
 260 static struct elevator_type iosched_zen = {
 261         .ops = {
 262                 .elevator_merge_req_fn          = zen_merged_requests,
 263                 .elevator_dispatch_fn           = zen_dispatch_requests,
 264                 .elevator_add_req_fn            = zen_add_request,
 265                 .elevator_former_req_fn         = elv_rb_former_request,
 266                 .elevator_latter_req_fn         = elv_rb_latter_request,
 267                 .elevator_init_fn               = zen_init_queue,
 268                 .elevator_exit_fn               = zen_exit_queue,
 269         },
 270         .elevator_attrs = zen_attrs,
 271         .elevator_name = "zen",
 272         .elevator_owner = THIS_MODULE,
 273 };
 274
 275 static int __init zen_init(void)
 276 {
 277         return elv_register(&iosched_zen);
 278 }
 279
 280 static void __exit zen_exit(void)
 281 {
 282         elv_unregister(&iosched_zen);
 283 }
 284
 285 module_init(zen_init);
 286 module_exit(zen_exit);
 287
 288
 289 MODULE_AUTHOR("Brandon Berhent");
 290 MODULE_LICENSE("GPL");
 291 MODULE_DESCRIPTION("Zen IO scheduler");
 292 MODULE_VERSION("1.1");
 293