block/vr-iosched.c

   1 /*
   2  * V(R) I/O Scheduler
   3  *
   4  * Copyright (C) 2007 Aaron Carroll <aaronc@gelato.unsw.edu.au>
   5  *
   6  *
   7  * The algorithm:
   8  *
   9  * The next request is decided based on its distance from the last
  10  * request, with a multiplicative penalty of `rev_penalty' applied
  11  * for reversing the head direction.  A rev_penalty of 1 means SSTF
  12  * behaviour. As this variable is increased, the algorithm approaches
  13  * pure SCAN.  Setting rev_penalty to 0 forces SCAN.
  14  *
  15  * Async and synch requests are not treated seperately.  Instead we
  16  * rely on deadlines to ensure fairness.
  17  *
  18  */
  19 #include <linux/kernel.h>
  20 #include <linux/fs.h>
  21 #include <linux/blkdev.h>
  22 #include <linux/elevator.h>
  23 #include <linux/bio.h>
  24 #include <linux/module.h>
  25 #include <linux/slab.h>
  26 #include <linux/init.h>
  27 #include <linux/compiler.h>
  28 #include <linux/rbtree.h>
  29
  30 enum vr_data_dir {
  31         ASYNC,
  32         SYNC,
  33 };
  34
  35 enum vr_head_dir {
  36         FORWARD,
  37         BACKWARD,
  38 };
  39
  40 static const int sync_expire = HZ / 2;  /* max time before a sync is submitted. */
  41 static const int async_expire = 5 * HZ; /* ditto for async, these limits are SOFT! */
  42 static const int fifo_batch = 16;
  43 static const int rev_penalty = 10;      /* penalty for reversing head direction */
  44
  45 struct vr_data {
  46         struct rb_root sort_list;
  47         struct list_head fifo_list[2];
  48
  49         struct request *next_rq;
  50         struct request *prev_rq;
  51
  52         unsigned int nbatched;
  53         sector_t last_sector;           /* head position */
  54         int head_dir;
  55
  56         /* tunables */
  57         int fifo_expire[2];
  58         int fifo_batch;
  59         int rev_penalty;
  60 };
  61
  62 static void vr_move_request(struct vr_data *, struct request *);
  63
  64 static inline struct vr_data *
  65 vr_get_data(struct request_queue *q)
  66 {
  67         return q->elevator->elevator_data;
  68 }
  69
  70 static void
  71 vr_add_rq_rb(struct vr_data *vd, struct request *rq)
  72 {
  73         struct request *alias = elv_rb_add(&vd->sort_list, rq);
  74
  75         if (unlikely(alias)) {
  76                 vr_move_request(vd, alias);
  77                 alias = elv_rb_add(&vd->sort_list, rq);
  78                 BUG_ON(alias);
  79         }
  80
  81         if (rq->sector >= vd->last_sector) {
  82                 if (!vd->next_rq || vd->next_rq->sector > rq->sector)
  83                         vd->next_rq = rq;
  84         }
  85         else {
  86                 if (!vd->prev_rq || vd->prev_rq->sector < rq->sector)
  87                         vd->prev_rq = rq;
  88         }
  89
  90         BUG_ON(vd->next_rq && vd->next_rq == vd->prev_rq);
  91         BUG_ON(vd->next_rq && vd->prev_rq && vd->next_rq->sector < vd->prev_rq->sector);
  92 }
  93
  94 static void
  95 vr_del_rq_rb(struct vr_data *vd, struct request *rq)
  96 {
  97         /*
  98          * We might be deleting our cached next request.
  99          * If so, find its sucessor.
 100          */
 101
 102         if (vd->next_rq == rq)
 103                 vd->next_rq = elv_rb_latter_request(NULL, rq);
 104         else if (vd->prev_rq == rq)
 105                 vd->prev_rq = elv_rb_former_request(NULL, rq);
 106
 107         BUG_ON(vd->next_rq && vd->next_rq == vd->prev_rq);
 108         BUG_ON(vd->next_rq && vd->prev_rq && vd->next_rq->sector < vd->prev_rq->sector);
 109
 110         elv_rb_del(&vd->sort_list, rq);
 111 }
 112
 113 /*
 114  * add rq to rbtree and fifo
 115  */
 116 static void
 117 vr_add_request(struct request_queue *q, struct request *rq)
 118 {
 119         struct vr_data *vd = vr_get_data(q);
 120         const int dir = rq_is_sync(rq);
 121
 122         vr_add_rq_rb(vd, rq);
 123
 124         if (vd->fifo_expire[dir]) {
 125                 rq_set_fifo_time(rq, jiffies + vd->fifo_expire[dir]);
 126                 list_add_tail(&rq->queuelist, &vd->fifo_list[dir]);
 127         }
 128 }
 129
 130 /*
 131  * remove rq from rbtree and fifo.
 132  */
 133 static void
 134 vr_remove_request(struct request_queue *q, struct request *rq)
 135 {
 136         struct vr_data *vd = vr_get_data(q);
 137
 138         rq_fifo_clear(rq);
 139         vr_del_rq_rb(vd, rq);
 140 }
 141
 142 static int
 143 vr_merge(struct request_queue *q, struct request **rqp, struct bio *bio)
 144 {
 145         sector_t sector = bio->bi_sector + bio_sectors(bio);
 146         struct vr_data *vd = vr_get_data(q);
 147         struct request *rq = elv_rb_find(&vd->sort_list, sector);
 148
 149         if (rq && elv_rq_merge_ok(rq, bio)) {
 150                 *rqp = rq;
 151                 return ELEVATOR_FRONT_MERGE;
 152         }
 153         return ELEVATOR_NO_MERGE;
 154 }
 155
 156 static void
 157 vr_merged_request(struct request_queue *q, struct request *req, int type)
 158 {
 159         struct vr_data *vd = vr_get_data(q);
 160
 161         /*
 162          * if the merge was a front merge, we need to reposition request
 163          */
 164         if (type == ELEVATOR_FRONT_MERGE) {
 165                 vr_del_rq_rb(vd, req);
 166                 vr_add_rq_rb(vd, req);
 167         }
 168 }
 169
 170 static void
 171 vr_merged_requests(struct request_queue *q, struct request *rq,
 172                         struct request *next)
 173 {
 174         /*
 175          * if next expires before rq, assign its expire time to rq
 176          * and move into next position (next will be deleted) in fifo
 177          */
 178         if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist)) {
 179                 if (time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
 180                         list_move(&rq->queuelist, &next->queuelist);
 181                         rq_set_fifo_time(rq, rq_fifo_time(next));
 182                 }
 183         }
 184
 185         vr_remove_request(q, next);
 186 }
 187
 188 /*
 189  * move an entry to dispatch queue
 190  */
 191 static void
 192 vr_move_request(struct vr_data *vd, struct request *rq)
 193 {
 194         struct request_queue *q = rq->q;
 195
 196         if (rq->sector > vd->last_sector)
 197                 vd->head_dir = FORWARD;
 198         else
 199                 vd->head_dir = BACKWARD;
 200
 201         vd->last_sector = rq->sector;
 202         vd->next_rq = elv_rb_latter_request(NULL, rq);
 203         vd->prev_rq = elv_rb_former_request(NULL, rq);
 204
 205         BUG_ON(vd->next_rq && vd->next_rq == vd->prev_rq);
 206
 207         vr_remove_request(q, rq);
 208         elv_dispatch_add_tail(q, rq);
 209         vd->nbatched++;
 210 }
 211
 212 /*
 213  * get the first expired request in direction ddir
 214  */
 215 static struct request *
 216 vr_expired_request(struct vr_data *vd, int ddir)
 217 {
 218         struct request *rq;
 219
 220         if (list_empty(&vd->fifo_list[ddir]))
 221                 return NULL;
 222
 223         rq = rq_entry_fifo(vd->fifo_list[ddir].next);
 224         if (time_after(jiffies, rq_fifo_time(rq)))
 225                 return rq;
 226
 227         return NULL;
 228 }
 229
 230 /*
 231  * Returns the oldest expired request
 232  */
 233 static struct request *
 234 vr_check_fifo(struct vr_data *vd)
 235 {
 236         struct request *rq_sync = vr_expired_request(vd, SYNC);
 237         struct request *rq_async = vr_expired_request(vd, ASYNC);
 238
 239         if (rq_async && rq_sync) {
 240                 if (time_after(rq_fifo_time(rq_async), rq_fifo_time(rq_sync)))
 241                         return rq_sync;
 242         }
 243         else if (rq_sync)
 244                 return rq_sync;
 245
 246         return rq_async;
 247 }
 248
 249 /*
 250  * Return the request with the lowest penalty
 251  */
 252 static struct request *
 253 vr_choose_request(struct vr_data *vd)
 254 {
 255         int penalty = (vd->rev_penalty) ? : INT_MAX;
 256         struct request *next = vd->next_rq;
 257         struct request *prev = vd->prev_rq;
 258         sector_t next_pen, prev_pen;
 259
 260         BUG_ON(prev && prev == next);
 261
 262         if (!prev)
 263                 return next;
 264         else if (!next)
 265                 return prev;
 266
 267         /* At this point both prev and next are defined and distinct */
 268
 269         next_pen = next->sector - vd->last_sector;
 270         prev_pen = vd->last_sector - prev->sector;
 271
 272         if (vd->head_dir == FORWARD)
 273                 next_pen /= penalty;
 274         else
 275                 prev_pen /= penalty;
 276
 277         if (next_pen <= prev_pen)
 278                 return next;
 279
 280         return prev;
 281 }
 282
 283 static int
 284 vr_dispatch_requests(struct request_queue *q, int force)
 285 {
 286         struct vr_data *vd = vr_get_data(q);
 287         struct request *rq = NULL;
 288
 289         /* Check for and issue expired requests */
 290         if (vd->nbatched > vd->fifo_batch) {
 291                 vd->nbatched = 0;
 292                 rq = vr_check_fifo(vd);
 293         }
 294
 295         if (!rq) {
 296                 rq = vr_choose_request(vd);
 297                 if (!rq)
 298                         return 0;
 299         }
 300
 301         vr_move_request(vd, rq);
 302
 303         return 1;
 304 }
 305
 306 static int
 307 vr_queue_empty(struct request_queue *q)
 308 {
 309         struct vr_data *vd = vr_get_data(q);
 310         return RB_EMPTY_ROOT(&vd->sort_list);
 311 }
 312
 313 static void
 314 vr_exit_queue(elevator_t *e)
 315 {
 316         struct vr_data *vd = e->elevator_data;
 317         BUG_ON(!RB_EMPTY_ROOT(&vd->sort_list));
 318         kfree(vd);
 319 }
 320
 321 /*
 322  * initialize elevator private data (vr_data).
 323  */
 324 static void *vr_init_queue(struct request_queue *q)
 325 {
 326         struct vr_data *vd;
 327
 328         vd = kmalloc_node(sizeof(*vd), GFP_KERNEL | __GFP_ZERO, q->node);
 329         if (!vd)
 330                 return NULL;
 331
 332         INIT_LIST_HEAD(&vd->fifo_list[SYNC]);
 333         INIT_LIST_HEAD(&vd->fifo_list[ASYNC]);
 334         vd->sort_list = RB_ROOT;
 335         vd->fifo_expire[SYNC] = sync_expire;
 336         vd->fifo_expire[ASYNC] = async_expire;
 337         vd->fifo_batch = fifo_batch;
 338         vd->rev_penalty = rev_penalty;
 339         return vd;
 340 }
 341
 342 /*
 343  * sysfs parts below
 344  */
 345
 346 static ssize_t
 347 vr_var_show(int var, char *page)
 348 {
 349         return sprintf(page, "%d\n", var);
 350 }
 351
 352 static ssize_t
 353 vr_var_store(int *var, const char *page, size_t count)
 354 {
 355         *var = simple_strtol(page, NULL, 10);
 356         return count;
 357 }
 358
 359 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV)                            \
 360 static ssize_t __FUNC(elevator_t *e, char *page)                        \
 361 {                                                                       \
 362         struct vr_data *vd = e->elevator_data;                          \
 363         int __data = __VAR;                                             \
 364         if (__CONV)                                                     \
 365                 __data = jiffies_to_msecs(__data);                      \
 366         return vr_var_show(__data, (page));                             \
 367 }
 368 SHOW_FUNCTION(vr_sync_expire_show, vd->fifo_expire[SYNC], 1);
 369 SHOW_FUNCTION(vr_async_expire_show, vd->fifo_expire[ASYNC], 1);
 370 SHOW_FUNCTION(vr_fifo_batch_show, vd->fifo_batch, 0);
 371 SHOW_FUNCTION(vr_rev_penalty_show, vd->rev_penalty, 0);
 372 #undef SHOW_FUNCTION
 373
 374 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)                 \
 375 static ssize_t __FUNC(elevator_t *e, const char *page, size_t count)    \
 376 {                                                                       \
 377         struct vr_data *vd = e->elevator_data;                          \
 378         int __data;                                                     \
 379         int ret = vr_var_store(&__data, (page), count);                 \
 380         if (__data < (MIN))                                             \
 381                 __data = (MIN);                                         \
 382         else if (__data > (MAX))                                        \
 383                 __data = (MAX);                                         \
 384         if (__CONV)                                                     \
 385                 *(__PTR) = msecs_to_jiffies(__data);                    \
 386         else                                                            \
 387                 *(__PTR) = __data;                                      \
 388         return ret;                                                     \
 389 }
 390 STORE_FUNCTION(vr_sync_expire_store, &vd->fifo_expire[SYNC], 0, INT_MAX, 1);
 391 STORE_FUNCTION(vr_async_expire_store, &vd->fifo_expire[ASYNC], 0, INT_MAX, 1);
 392 STORE_FUNCTION(vr_fifo_batch_store, &vd->fifo_batch, 0, INT_MAX, 0);
 393 STORE_FUNCTION(vr_rev_penalty_store, &vd->rev_penalty, 0, INT_MAX, 0);
 394 #undef STORE_FUNCTION
 395
 396 #define DD_ATTR(name) \
 397         __ATTR(name, S_IRUGO|S_IWUSR, vr_##name##_show, \
 398                                       vr_##name##_store)
 399
 400 static struct elv_fs_entry vr_attrs[] = {
 401         DD_ATTR(sync_expire),
 402         DD_ATTR(async_expire),
 403         DD_ATTR(fifo_batch),
 404         DD_ATTR(rev_penalty),
 405         __ATTR_NULL
 406 };
 407
 408 static struct elevator_type iosched_vr = {
 409         .ops = {
 410                 .elevator_merge_fn =            vr_merge,
 411                 .elevator_merged_fn =           vr_merged_request,
 412                 .elevator_merge_req_fn =        vr_merged_requests,
 413                 .elevator_dispatch_fn =         vr_dispatch_requests,
 414                 .elevator_add_req_fn =          vr_add_request,
 415                 .elevator_queue_empty_fn =      vr_queue_empty,
 416                 .elevator_former_req_fn =       elv_rb_former_request,
 417                 .elevator_latter_req_fn =       elv_rb_latter_request,
 418                 .elevator_init_fn =             vr_init_queue,
 419                 .elevator_exit_fn =             vr_exit_queue,
 420         },
 421
 422         .elevator_attrs = vr_attrs,
 423         .elevator_name = "vr",
 424         .elevator_owner = THIS_MODULE,
 425 };
 426
 427 static int __init vr_init(void)
 428 {
 429         elv_register(&iosched_vr);
 430
 431         return 0;
 432 }
 433
 434 static void __exit vr_exit(void)
 435 {
 436         elv_unregister(&iosched_vr);
 437 }
 438
 439 module_init(vr_init);
 440 module_exit(vr_exit);
 441
 442 MODULE_AUTHOR("Aaron Carroll");
 443 MODULE_LICENSE("GPL");
 444 MODULE_DESCRIPTION("V(R) IO scheduler");
 445