block/blk-throttle.c

   1 /*
   2  * Interface for controlling IO bandwidth on a request queue
   3  *
   4  * Copyright (C) 2010 Vivek Goyal <vgoyal@redhat.com>
   5  */
   6
   7 #include <linux/module.h>
   8 #include <linux/slab.h>
   9 #include <linux/blkdev.h>
  10 #include <linux/bio.h>
  11 #include <linux/blktrace_api.h>
  12 #include "blk-cgroup.h"
  13
  14 /* Max dispatch from a group in 1 round */
  15 static int throtl_grp_quantum = 8;
  16
  17 /* Total max dispatch from all groups in one round */
  18 static int throtl_quantum = 32;
  19
  20 /* Throttling is performed over 100ms slice and after that slice is renewed */
  21 static unsigned long throtl_slice = HZ/10;      /* 100 ms */
  22
  23 /* A workqueue to queue throttle related work */
  24 static struct workqueue_struct *kthrotld_workqueue;
  25 static void throtl_schedule_delayed_work(struct throtl_data *td,
  26                                 unsigned long delay);
  27
  28 struct throtl_rb_root {
  29         struct rb_root rb;
  30         struct rb_node *left;
  31         unsigned int count;
  32         unsigned long min_disptime;
  33 };
  34
  35 #define THROTL_RB_ROOT  (struct throtl_rb_root) { .rb = RB_ROOT, .left = NULL, \
  36                         .count = 0, .min_disptime = 0}
  37
  38 #define rb_entry_tg(node)       rb_entry((node), struct throtl_grp, rb_node)
  39
  40 struct throtl_grp {
  41         /* List of throtl groups on the request queue*/
  42         struct hlist_node tg_node;
  43
  44         /* active throtl group service_tree member */
  45         struct rb_node rb_node;
  46
  47         /*
  48          * Dispatch time in jiffies. This is the estimated time when group
  49          * will unthrottle and is ready to dispatch more bio. It is used as
  50          * key to sort active groups in service tree.
  51          */
  52         unsigned long disptime;
  53
  54         struct blkio_group blkg;
  55         atomic_t ref;
  56         unsigned int flags;
  57
  58         /* Two lists for READ and WRITE */
  59         struct bio_list bio_lists[2];
  60
  61         /* Number of queued bios on READ and WRITE lists */
  62         unsigned int nr_queued[2];
  63
  64         /* bytes per second rate limits */
  65         uint64_t bps[2];
  66
  67         /* IOPS limits */
  68         unsigned int iops[2];
  69
  70         /* Number of bytes disptached in current slice */
  71         uint64_t bytes_disp[2];
  72         /* Number of bio's dispatched in current slice */
  73         unsigned int io_disp[2];
  74
  75         /* When did we start a new slice */
  76         unsigned long slice_start[2];
  77         unsigned long slice_end[2];
  78
  79         /* Some throttle limits got updated for the group */
  80         int limits_changed;
  81 };
  82
  83 struct throtl_data
  84 {
  85         /* List of throtl groups */
  86         struct hlist_head tg_list;
  87
  88         /* service tree for active throtl groups */
  89         struct throtl_rb_root tg_service_tree;
  90
  91         struct throtl_grp *root_tg;
  92         struct request_queue *queue;
  93
  94         /* Total Number of queued bios on READ and WRITE lists */
  95         unsigned int nr_queued[2];
  96
  97         /*
  98          * number of total undestroyed groups
  99          */
 100         unsigned int nr_undestroyed_grps;
 101
 102         /* Work for dispatching throttled bios */
 103         struct delayed_work throtl_work;
 104
 105         int limits_changed;
 106 };
 107
 108 enum tg_state_flags {
 109         THROTL_TG_FLAG_on_rr = 0,       /* on round-robin busy list */
 110 };
 111
 112 #define THROTL_TG_FNS(name)                                             \
 113 static inline void throtl_mark_tg_##name(struct throtl_grp *tg)         \
 114 {                                                                       \
 115         (tg)->flags |= (1 << THROTL_TG_FLAG_##name);                    \
 116 }                                                                       \
 117 static inline void throtl_clear_tg_##name(struct throtl_grp *tg)        \
 118 {                                                                       \
 119         (tg)->flags &= ~(1 << THROTL_TG_FLAG_##name);                   \
 120 }                                                                       \
 121 static inline int throtl_tg_##name(const struct throtl_grp *tg)         \
 122 {                                                                       \
 123         return ((tg)->flags & (1 << THROTL_TG_FLAG_##name)) != 0;       \
 124 }
 125
 126 THROTL_TG_FNS(on_rr);
 127
 128 #define throtl_log_tg(td, tg, fmt, args...)                             \
 129         blk_add_trace_msg((td)->queue, "throtl %s " fmt,                \
 130                                 blkg_path(&(tg)->blkg), ##args);        \
 131
 132 #define throtl_log(td, fmt, args...)    \
 133         blk_add_trace_msg((td)->queue, "throtl " fmt, ##args)
 134
 135 static inline struct throtl_grp *tg_of_blkg(struct blkio_group *blkg)
 136 {
 137         if (blkg)
 138                 return container_of(blkg, struct throtl_grp, blkg);
 139
 140         return NULL;
 141 }
 142
 143 static inline int total_nr_queued(struct throtl_data *td)
 144 {
 145         return (td->nr_queued[0] + td->nr_queued[1]);
 146 }
 147
 148 static inline struct throtl_grp *throtl_ref_get_tg(struct throtl_grp *tg)
 149 {
 150         atomic_inc(&tg->ref);
 151         return tg;
 152 }
 153
 154 static void throtl_put_tg(struct throtl_grp *tg)
 155 {
 156         BUG_ON(atomic_read(&tg->ref) <= 0);
 157         if (!atomic_dec_and_test(&tg->ref))
 158                 return;
 159         kfree(tg);
 160 }
 161
 162 static void throtl_init_group(struct throtl_grp *tg)
 163 {
 164         INIT_HLIST_NODE(&tg->tg_node);
 165         RB_CLEAR_NODE(&tg->rb_node);
 166         bio_list_init(&tg->bio_lists[0]);
 167         bio_list_init(&tg->bio_lists[1]);
 168         tg->limits_changed = false;
 169
 170         /* Practically unlimited BW */
 171         tg->bps[0] = tg->bps[1] = -1;
 172         tg->iops[0] = tg->iops[1] = -1;
 173
 174         /*
 175          * Take the initial reference that will be released on destroy
 176          * This can be thought of a joint reference by cgroup and
 177          * request queue which will be dropped by either request queue
 178          * exit or cgroup deletion path depending on who is exiting first.
 179          */
 180         atomic_set(&tg->ref, 1);
 181 }
 182
 183 /* Should be called with rcu read lock held (needed for blkcg) */
 184 static void
 185 throtl_add_group_to_td_list(struct throtl_data *td, struct throtl_grp *tg)
 186 {
 187         hlist_add_head(&tg->tg_node, &td->tg_list);
 188         td->nr_undestroyed_grps++;
 189 }
 190
 191 static void
 192 __throtl_tg_fill_dev_details(struct throtl_data *td, struct throtl_grp *tg)
 193 {
 194         struct backing_dev_info *bdi = &td->queue->backing_dev_info;
 195         unsigned int major, minor;
 196
 197         if (!tg || tg->blkg.dev)
 198                 return;
 199
 200         /*
 201          * Fill in device details for a group which might not have been
 202          * filled at group creation time as queue was being instantiated
 203          * and driver had not attached a device yet
 204          */
 205         if (bdi->dev && dev_name(bdi->dev)) {
 206                 sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
 207                 tg->blkg.dev = MKDEV(major, minor);
 208         }
 209 }
 210
 211 static void throtl_init_add_tg_lists(struct throtl_data *td,
 212                         struct throtl_grp *tg, struct blkio_cgroup *blkcg)
 213 {
 214         __throtl_tg_fill_dev_details(td, tg);
 215
 216         /* Add group onto cgroup list */
 217         blkiocg_add_blkio_group(blkcg, &tg->blkg, (void *)td,
 218                                 tg->blkg.dev, BLKIO_POLICY_THROTL);
 219
 220         tg->bps[READ] = blkcg_get_read_bps(blkcg, tg->blkg.dev);
 221         tg->bps[WRITE] = blkcg_get_write_bps(blkcg, tg->blkg.dev);
 222         tg->iops[READ] = blkcg_get_read_iops(blkcg, tg->blkg.dev);
 223         tg->iops[WRITE] = blkcg_get_write_iops(blkcg, tg->blkg.dev);
 224
 225         throtl_add_group_to_td_list(td, tg);
 226 }
 227
 228 /* Should be called without queue lock and outside of rcu period */
 229 static struct throtl_grp *throtl_alloc_tg(struct throtl_data *td)
 230 {
 231         struct throtl_grp *tg = NULL;
 232
 233         tg = kzalloc_node(sizeof(*tg), GFP_ATOMIC, td->queue->node);
 234         if (!tg)
 235                 return NULL;
 236
 237         throtl_init_group(tg);
 238         return tg;
 239 }
 240
 241 static struct
 242 throtl_grp *throtl_find_tg(struct throtl_data *td, struct blkio_cgroup *blkcg)
 243 {
 244         struct throtl_grp *tg = NULL;
 245         void *key = td;
 246
 247         /*
 248          * This is the common case when there are no blkio cgroups.
 249          * Avoid lookup in this case
 250          */
 251         if (blkcg == &blkio_root_cgroup)
 252                 tg = td->root_tg;
 253         else
 254                 tg = tg_of_blkg(blkiocg_lookup_group(blkcg, key));
 255
 256         __throtl_tg_fill_dev_details(td, tg);
 257         return tg;
 258 }
 259
 260 /*
 261  * This function returns with queue lock unlocked in case of error, like
 262  * request queue is no more
 263  */
 264 static struct throtl_grp * throtl_get_tg(struct throtl_data *td)
 265 {
 266         struct throtl_grp *tg = NULL, *__tg = NULL;
 267         struct blkio_cgroup *blkcg;
 268         struct request_queue *q = td->queue;
 269
 270         rcu_read_lock();
 271         blkcg = task_blkio_cgroup(current);
 272         tg = throtl_find_tg(td, blkcg);
 273         if (tg) {
 274                 rcu_read_unlock();
 275                 return tg;
 276         }
 277
 278         /*
 279          * Need to allocate a group. Allocation of group also needs allocation
 280          * of per cpu stats which in-turn takes a mutex() and can block. Hence
 281          * we need to drop rcu lock and queue_lock before we call alloc
 282          *
 283          * Take the request queue reference to make sure queue does not
 284          * go away once we return from allocation.
 285          */
 286         blk_get_queue(q);
 287         rcu_read_unlock();
 288         spin_unlock_irq(q->queue_lock);
 289
 290         tg = throtl_alloc_tg(td);
 291         /*
 292          * We might have slept in group allocation. Make sure queue is not
 293          * dead
 294          */
 295         if (unlikely(test_bit(QUEUE_FLAG_DEAD, &q->queue_flags))) {
 296                 blk_put_queue(q);
 297                 if (tg)
 298                         kfree(tg);
 299
 300                 return ERR_PTR(-ENODEV);
 301         }
 302         blk_put_queue(q);
 303
 304         /* Group allocated and queue is still alive. take the lock */
 305         spin_lock_irq(q->queue_lock);
 306
 307         /*
 308          * Initialize the new group. After sleeping, read the blkcg again.
 309          */
 310         rcu_read_lock();
 311         blkcg = task_blkio_cgroup(current);
 312
 313         /*
 314          * If some other thread already allocated the group while we were
 315          * not holding queue lock, free up the group
 316          */
 317         __tg = throtl_find_tg(td, blkcg);
 318
 319         if (__tg) {
 320                 kfree(tg);
 321                 rcu_read_unlock();
 322                 return __tg;
 323         }
 324
 325         /* Group allocation failed. Account the IO to root group */
 326         if (!tg) {
 327                 tg = td->root_tg;
 328                 return tg;
 329         }
 330
 331         throtl_init_add_tg_lists(td, tg, blkcg);
 332         rcu_read_unlock();
 333         return tg;
 334 }
 335
 336 static struct throtl_grp *throtl_rb_first(struct throtl_rb_root *root)
 337 {
 338         /* Service tree is empty */
 339         if (!root->count)
 340                 return NULL;
 341
 342         if (!root->left)
 343                 root->left = rb_first(&root->rb);
 344
 345         if (root->left)
 346                 return rb_entry_tg(root->left);
 347
 348         return NULL;
 349 }
 350
 351 static void rb_erase_init(struct rb_node *n, struct rb_root *root)
 352 {
 353         rb_erase(n, root);
 354         RB_CLEAR_NODE(n);
 355 }
 356
 357 static void throtl_rb_erase(struct rb_node *n, struct throtl_rb_root *root)
 358 {
 359         if (root->left == n)
 360                 root->left = NULL;
 361         rb_erase_init(n, &root->rb);
 362         --root->count;
 363 }
 364
 365 static void update_min_dispatch_time(struct throtl_rb_root *st)
 366 {
 367         struct throtl_grp *tg;
 368
 369         tg = throtl_rb_first(st);
 370         if (!tg)
 371                 return;
 372
 373         st->min_disptime = tg->disptime;
 374 }
 375
 376 static void
 377 tg_service_tree_add(struct throtl_rb_root *st, struct throtl_grp *tg)
 378 {
 379         struct rb_node **node = &st->rb.rb_node;
 380         struct rb_node *parent = NULL;
 381         struct throtl_grp *__tg;
 382         unsigned long key = tg->disptime;
 383         int left = 1;
 384
 385         while (*node != NULL) {
 386                 parent = *node;
 387                 __tg = rb_entry_tg(parent);
 388
 389                 if (time_before(key, __tg->disptime))
 390                         node = &parent->rb_left;
 391                 else {
 392                         node = &parent->rb_right;
 393                         left = 0;
 394                 }
 395         }
 396
 397         if (left)
 398                 st->left = &tg->rb_node;
 399
 400         rb_link_node(&tg->rb_node, parent, node);
 401         rb_insert_color(&tg->rb_node, &st->rb);
 402 }
 403
 404 static void __throtl_enqueue_tg(struct throtl_data *td, struct throtl_grp *tg)
 405 {
 406         struct throtl_rb_root *st = &td->tg_service_tree;
 407
 408         tg_service_tree_add(st, tg);
 409         throtl_mark_tg_on_rr(tg);
 410         st->count++;
 411 }
 412
 413 static void throtl_enqueue_tg(struct throtl_data *td, struct throtl_grp *tg)
 414 {
 415         if (!throtl_tg_on_rr(tg))
 416                 __throtl_enqueue_tg(td, tg);
 417 }
 418
 419 static void __throtl_dequeue_tg(struct throtl_data *td, struct throtl_grp *tg)
 420 {
 421         throtl_rb_erase(&tg->rb_node, &td->tg_service_tree);
 422         throtl_clear_tg_on_rr(tg);
 423 }
 424
 425 static void throtl_dequeue_tg(struct throtl_data *td, struct throtl_grp *tg)
 426 {
 427         if (throtl_tg_on_rr(tg))
 428                 __throtl_dequeue_tg(td, tg);
 429 }
 430
 431 static void throtl_schedule_next_dispatch(struct throtl_data *td)
 432 {
 433         struct throtl_rb_root *st = &td->tg_service_tree;
 434
 435         /*
 436          * If there are more bios pending, schedule more work.
 437          */
 438         if (!total_nr_queued(td))
 439                 return;
 440
 441         BUG_ON(!st->count);
 442
 443         update_min_dispatch_time(st);
 444
 445         if (time_before_eq(st->min_disptime, jiffies))
 446                 throtl_schedule_delayed_work(td, 0);
 447         else
 448                 throtl_schedule_delayed_work(td, (st->min_disptime - jiffies));
 449 }
 450
 451 static inline void
 452 throtl_start_new_slice(struct throtl_data *td, struct throtl_grp *tg, bool rw)
 453 {
 454         tg->bytes_disp[rw] = 0;
 455         tg->io_disp[rw] = 0;
 456         tg->slice_start[rw] = jiffies;
 457         tg->slice_end[rw] = jiffies + throtl_slice;
 458         throtl_log_tg(td, tg, "[%c] new slice start=%lu end=%lu jiffies=%lu",
 459                         rw == READ ? 'R' : 'W', tg->slice_start[rw],
 460                         tg->slice_end[rw], jiffies);
 461 }
 462
 463 static inline void throtl_set_slice_end(struct throtl_data *td,
 464                 struct throtl_grp *tg, bool rw, unsigned long jiffy_end)
 465 {
 466         tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
 467 }
 468
 469 static inline void throtl_extend_slice(struct throtl_data *td,
 470                 struct throtl_grp *tg, bool rw, unsigned long jiffy_end)
 471 {
 472         tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
 473         throtl_log_tg(td, tg, "[%c] extend slice start=%lu end=%lu jiffies=%lu",
 474                         rw == READ ? 'R' : 'W', tg->slice_start[rw],
 475                         tg->slice_end[rw], jiffies);
 476 }
 477
 478 /* Determine if previously allocated or extended slice is complete or not */
 479 static bool
 480 throtl_slice_used(struct throtl_data *td, struct throtl_grp *tg, bool rw)
 481 {
 482         if (time_in_range(jiffies, tg->slice_start[rw], tg->slice_end[rw]))
 483                 return 0;
 484
 485         return 1;
 486 }
 487
 488 /* Trim the used slices and adjust slice start accordingly */
 489 static inline void
 490 throtl_trim_slice(struct throtl_data *td, struct throtl_grp *tg, bool rw)
 491 {
 492         unsigned long nr_slices, time_elapsed, io_trim;
 493         u64 bytes_trim, tmp;
 494
 495         BUG_ON(time_before(tg->slice_end[rw], tg->slice_start[rw]));
 496
 497         /*
 498          * If bps are unlimited (-1), then time slice don't get
 499          * renewed. Don't try to trim the slice if slice is used. A new
 500          * slice will start when appropriate.
 501          */
 502         if (throtl_slice_used(td, tg, rw))
 503                 return;
 504
 505         /*
 506          * A bio has been dispatched. Also adjust slice_end. It might happen
 507          * that initially cgroup limit was very low resulting in high
 508          * slice_end, but later limit was bumped up and bio was dispached
 509          * sooner, then we need to reduce slice_end. A high bogus slice_end
 510          * is bad because it does not allow new slice to start.
 511          */
 512
 513         throtl_set_slice_end(td, tg, rw, jiffies + throtl_slice);
 514
 515         time_elapsed = jiffies - tg->slice_start[rw];
 516
 517         nr_slices = time_elapsed / throtl_slice;
 518
 519         if (!nr_slices)
 520                 return;
 521         tmp = tg->bps[rw] * throtl_slice * nr_slices;
 522         do_div(tmp, HZ);
 523         bytes_trim = tmp;
 524
 525         io_trim = (tg->iops[rw] * throtl_slice * nr_slices)/HZ;
 526
 527         if (!bytes_trim && !io_trim)
 528                 return;
 529
 530         if (tg->bytes_disp[rw] >= bytes_trim)
 531                 tg->bytes_disp[rw] -= bytes_trim;
 532         else
 533                 tg->bytes_disp[rw] = 0;
 534
 535         if (tg->io_disp[rw] >= io_trim)
 536                 tg->io_disp[rw] -= io_trim;
 537         else
 538                 tg->io_disp[rw] = 0;
 539
 540         tg->slice_start[rw] += nr_slices * throtl_slice;
 541
 542         throtl_log_tg(td, tg, "[%c] trim slice nr=%lu bytes=%llu io=%lu"
 543                         " start=%lu end=%lu jiffies=%lu",
 544                         rw == READ ? 'R' : 'W', nr_slices, bytes_trim, io_trim,
 545                         tg->slice_start[rw], tg->slice_end[rw], jiffies);
 546 }
 547
 548 static bool tg_with_in_iops_limit(struct throtl_data *td, struct throtl_grp *tg,
 549                 struct bio *bio, unsigned long *wait)
 550 {
 551         bool rw = bio_data_dir(bio);
 552         unsigned int io_allowed;
 553         unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
 554         u64 tmp;
 555
 556         jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
 557
 558         /* Slice has just started. Consider one slice interval */
 559         if (!jiffy_elapsed)
 560                 jiffy_elapsed_rnd = throtl_slice;
 561
 562         jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
 563
 564         /*
 565          * jiffy_elapsed_rnd should not be a big value as minimum iops can be
 566          * 1 then at max jiffy elapsed should be equivalent of 1 second as we
 567          * will allow dispatch after 1 second and after that slice should
 568          * have been trimmed.
 569          */
 570
 571         tmp = (u64)tg->iops[rw] * jiffy_elapsed_rnd;
 572         do_div(tmp, HZ);
 573
 574         if (tmp > UINT_MAX)
 575                 io_allowed = UINT_MAX;
 576         else
 577                 io_allowed = tmp;
 578
 579         if (tg->io_disp[rw] + 1 <= io_allowed) {
 580                 if (wait)
 581                         *wait = 0;
 582                 return 1;
 583         }
 584
 585         /* Calc approx time to dispatch */
 586         jiffy_wait = ((tg->io_disp[rw] + 1) * HZ)/tg->iops[rw] + 1;
 587
 588         if (jiffy_wait > jiffy_elapsed)
 589                 jiffy_wait = jiffy_wait - jiffy_elapsed;
 590         else
 591                 jiffy_wait = 1;
 592
 593         if (wait)
 594                 *wait = jiffy_wait;
 595         return 0;
 596 }
 597
 598 static bool tg_with_in_bps_limit(struct throtl_data *td, struct throtl_grp *tg,
 599                 struct bio *bio, unsigned long *wait)
 600 {
 601         bool rw = bio_data_dir(bio);
 602         u64 bytes_allowed, extra_bytes, tmp;
 603         unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
 604
 605         jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
 606
 607         /* Slice has just started. Consider one slice interval */
 608         if (!jiffy_elapsed)
 609                 jiffy_elapsed_rnd = throtl_slice;
 610
 611         jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
 612
 613         tmp = tg->bps[rw] * jiffy_elapsed_rnd;
 614         do_div(tmp, HZ);
 615         bytes_allowed = tmp;
 616
 617         if (tg->bytes_disp[rw] + bio->bi_size <= bytes_allowed) {
 618                 if (wait)
 619                         *wait = 0;
 620                 return 1;
 621         }
 622
 623         /* Calc approx time to dispatch */
 624         extra_bytes = tg->bytes_disp[rw] + bio->bi_size - bytes_allowed;
 625         jiffy_wait = div64_u64(extra_bytes * HZ, tg->bps[rw]);
 626
 627         if (!jiffy_wait)
 628                 jiffy_wait = 1;
 629
 630         /*
 631          * This wait time is without taking into consideration the rounding
 632          * up we did. Add that time also.
 633          */
 634         jiffy_wait = jiffy_wait + (jiffy_elapsed_rnd - jiffy_elapsed);
 635         if (wait)
 636                 *wait = jiffy_wait;
 637         return 0;
 638 }
 639
 640 /*
 641  * Returns whether one can dispatch a bio or not. Also returns approx number
 642  * of jiffies to wait before this bio is with-in IO rate and can be dispatched
 643  */
 644 static bool tg_may_dispatch(struct throtl_data *td, struct throtl_grp *tg,
 645                                 struct bio *bio, unsigned long *wait)
 646 {
 647         bool rw = bio_data_dir(bio);
 648         unsigned long bps_wait = 0, iops_wait = 0, max_wait = 0;
 649
 650         /*
 651          * Currently whole state machine of group depends on first bio
 652          * queued in the group bio list. So one should not be calling
 653          * this function with a different bio if there are other bios
 654          * queued.
 655          */
 656         BUG_ON(tg->nr_queued[rw] && bio != bio_list_peek(&tg->bio_lists[rw]));
 657
 658         /* If tg->bps = -1, then BW is unlimited */
 659         if (tg->bps[rw] == -1 && tg->iops[rw] == -1) {
 660                 if (wait)
 661                         *wait = 0;
 662                 return 1;
 663         }
 664
 665         /*
 666          * If previous slice expired, start a new one otherwise renew/extend
 667          * existing slice to make sure it is at least throtl_slice interval
 668          * long since now.
 669          */
 670         if (throtl_slice_used(td, tg, rw))
 671                 throtl_start_new_slice(td, tg, rw);
 672         else {
 673                 if (time_before(tg->slice_end[rw], jiffies + throtl_slice))
 674                         throtl_extend_slice(td, tg, rw, jiffies + throtl_slice);
 675         }
 676
 677         if (tg_with_in_bps_limit(td, tg, bio, &bps_wait)
 678             && tg_with_in_iops_limit(td, tg, bio, &iops_wait)) {
 679                 if (wait)
 680                         *wait = 0;
 681                 return 1;
 682         }
 683
 684         max_wait = max(bps_wait, iops_wait);
 685
 686         if (wait)
 687                 *wait = max_wait;
 688
 689         if (time_before(tg->slice_end[rw], jiffies + max_wait))
 690                 throtl_extend_slice(td, tg, rw, jiffies + max_wait);
 691
 692         return 0;
 693 }
 694
 695 static void throtl_charge_bio(struct throtl_grp *tg, struct bio *bio)
 696 {
 697         bool rw = bio_data_dir(bio);
 698         bool sync = bio->bi_rw & REQ_SYNC;
 699
 700         /* Charge the bio to the group */
 701         tg->bytes_disp[rw] += bio->bi_size;
 702         tg->io_disp[rw]++;
 703
 704         /*
 705          * TODO: This will take blkg->stats_lock. Figure out a way
 706          * to avoid this cost.
 707          */
 708         blkiocg_update_dispatch_stats(&tg->blkg, bio->bi_size, rw, sync);
 709 }
 710
 711 static void throtl_add_bio_tg(struct throtl_data *td, struct throtl_grp *tg,
 712                         struct bio *bio)
 713 {
 714         bool rw = bio_data_dir(bio);
 715
 716         bio_list_add(&tg->bio_lists[rw], bio);
 717         /* Take a bio reference on tg */
 718         throtl_ref_get_tg(tg);
 719         tg->nr_queued[rw]++;
 720         td->nr_queued[rw]++;
 721         throtl_enqueue_tg(td, tg);
 722 }
 723
 724 static void tg_update_disptime(struct throtl_data *td, struct throtl_grp *tg)
 725 {
 726         unsigned long read_wait = -1, write_wait = -1, min_wait = -1, disptime;
 727         struct bio *bio;
 728
 729         if ((bio = bio_list_peek(&tg->bio_lists[READ])))
 730                 tg_may_dispatch(td, tg, bio, &read_wait);
 731
 732         if ((bio = bio_list_peek(&tg->bio_lists[WRITE])))
 733                 tg_may_dispatch(td, tg, bio, &write_wait);
 734
 735         min_wait = min(read_wait, write_wait);
 736         disptime = jiffies + min_wait;
 737
 738         /* Update dispatch time */
 739         throtl_dequeue_tg(td, tg);
 740         tg->disptime = disptime;
 741         throtl_enqueue_tg(td, tg);
 742 }
 743
 744 static void tg_dispatch_one_bio(struct throtl_data *td, struct throtl_grp *tg,
 745                                 bool rw, struct bio_list *bl)
 746 {
 747         struct bio *bio;
 748
 749         bio = bio_list_pop(&tg->bio_lists[rw]);
 750         tg->nr_queued[rw]--;
 751         /* Drop bio reference on tg */
 752         throtl_put_tg(tg);
 753
 754         BUG_ON(td->nr_queued[rw] <= 0);
 755         td->nr_queued[rw]--;
 756
 757         throtl_charge_bio(tg, bio);
 758         bio_list_add(bl, bio);
 759         bio->bi_rw |= REQ_THROTTLED;
 760
 761         throtl_trim_slice(td, tg, rw);
 762 }
 763
 764 static int throtl_dispatch_tg(struct throtl_data *td, struct throtl_grp *tg,
 765                                 struct bio_list *bl)
 766 {
 767         unsigned int nr_reads = 0, nr_writes = 0;
 768         unsigned int max_nr_reads = throtl_grp_quantum*3/4;
 769         unsigned int max_nr_writes = throtl_grp_quantum - max_nr_reads;
 770         struct bio *bio;
 771
 772         /* Try to dispatch 75% READS and 25% WRITES */
 773
 774         while ((bio = bio_list_peek(&tg->bio_lists[READ]))
 775                 && tg_may_dispatch(td, tg, bio, NULL)) {
 776
 777                 tg_dispatch_one_bio(td, tg, bio_data_dir(bio), bl);
 778                 nr_reads++;
 779
 780                 if (nr_reads >= max_nr_reads)
 781                         break;
 782         }
 783
 784         while ((bio = bio_list_peek(&tg->bio_lists[WRITE]))
 785                 && tg_may_dispatch(td, tg, bio, NULL)) {
 786
 787                 tg_dispatch_one_bio(td, tg, bio_data_dir(bio), bl);
 788                 nr_writes++;
 789
 790                 if (nr_writes >= max_nr_writes)
 791                         break;
 792         }
 793
 794         return nr_reads + nr_writes;
 795 }
 796
 797 static int throtl_select_dispatch(struct throtl_data *td, struct bio_list *bl)
 798 {
 799         unsigned int nr_disp = 0;
 800         struct throtl_grp *tg;
 801         struct throtl_rb_root *st = &td->tg_service_tree;
 802
 803         while (1) {
 804                 tg = throtl_rb_first(st);
 805
 806                 if (!tg)
 807                         break;
 808
 809                 if (time_before(jiffies, tg->disptime))
 810                         break;
 811
 812                 throtl_dequeue_tg(td, tg);
 813
 814                 nr_disp += throtl_dispatch_tg(td, tg, bl);
 815
 816                 if (tg->nr_queued[0] || tg->nr_queued[1]) {
 817                         tg_update_disptime(td, tg);
 818                         throtl_enqueue_tg(td, tg);
 819                 }
 820
 821                 if (nr_disp >= throtl_quantum)
 822                         break;
 823         }
 824
 825         return nr_disp;
 826 }
 827
 828 static void throtl_process_limit_change(struct throtl_data *td)
 829 {
 830         struct throtl_grp *tg;
 831         struct hlist_node *pos, *n;
 832
 833         if (!td->limits_changed)
 834                 return;
 835
 836         xchg(&td->limits_changed, false);
 837
 838         throtl_log(td, "limits changed");
 839
 840         hlist_for_each_entry_safe(tg, pos, n, &td->tg_list, tg_node) {
 841                 if (!tg->limits_changed)
 842                         continue;
 843
 844                 if (!xchg(&tg->limits_changed, false))
 845                         continue;
 846
 847                 throtl_log_tg(td, tg, "limit change rbps=%llu wbps=%llu"
 848                         " riops=%u wiops=%u", tg->bps[READ], tg->bps[WRITE],
 849                         tg->iops[READ], tg->iops[WRITE]);
 850
 851                 /*
 852                  * Restart the slices for both READ and WRITES. It
 853                  * might happen that a group's limit are dropped
 854                  * suddenly and we don't want to account recently
 855                  * dispatched IO with new low rate
 856                  */
 857                 throtl_start_new_slice(td, tg, 0);
 858                 throtl_start_new_slice(td, tg, 1);
 859
 860                 if (throtl_tg_on_rr(tg))
 861                         tg_update_disptime(td, tg);
 862         }
 863 }
 864
 865 /* Dispatch throttled bios. Should be called without queue lock held. */
 866 static int throtl_dispatch(struct request_queue *q)
 867 {
 868         struct throtl_data *td = q->td;
 869         unsigned int nr_disp = 0;
 870         struct bio_list bio_list_on_stack;
 871         struct bio *bio;
 872         struct blk_plug plug;
 873
 874         spin_lock_irq(q->queue_lock);
 875
 876         throtl_process_limit_change(td);
 877
 878         if (!total_nr_queued(td))
 879                 goto out;
 880
 881         bio_list_init(&bio_list_on_stack);
 882
 883         throtl_log(td, "dispatch nr_queued=%lu read=%u write=%u",
 884                         total_nr_queued(td), td->nr_queued[READ],
 885                         td->nr_queued[WRITE]);
 886
 887         nr_disp = throtl_select_dispatch(td, &bio_list_on_stack);
 888
 889         if (nr_disp)
 890                 throtl_log(td, "bios disp=%u", nr_disp);
 891
 892         throtl_schedule_next_dispatch(td);
 893 out:
 894         spin_unlock_irq(q->queue_lock);
 895
 896         /*
 897          * If we dispatched some requests, unplug the queue to make sure
 898          * immediate dispatch
 899          */
 900         if (nr_disp) {
 901                 blk_start_plug(&plug);
 902                 while((bio = bio_list_pop(&bio_list_on_stack)))
 903                         generic_make_request(bio);
 904                 blk_finish_plug(&plug);
 905         }
 906         return nr_disp;
 907 }
 908
 909 void blk_throtl_work(struct work_struct *work)
 910 {
 911         struct throtl_data *td = container_of(work, struct throtl_data,
 912                                         throtl_work.work);
 913         struct request_queue *q = td->queue;
 914
 915         throtl_dispatch(q);
 916 }
 917
 918 /* Call with queue lock held */
 919 static void
 920 throtl_schedule_delayed_work(struct throtl_data *td, unsigned long delay)
 921 {
 922
 923         struct delayed_work *dwork = &td->throtl_work;
 924
 925         /* schedule work if limits changed even if no bio is queued */
 926         if (total_nr_queued(td) > 0 || td->limits_changed) {
 927                 /*
 928                  * We might have a work scheduled to be executed in future.
 929                  * Cancel that and schedule a new one.
 930                  */
 931                 __cancel_delayed_work(dwork);
 932                 queue_delayed_work(kthrotld_workqueue, dwork, delay);
 933                 throtl_log(td, "schedule work. delay=%lu jiffies=%lu",
 934                                 delay, jiffies);
 935         }
 936 }
 937
 938 static void
 939 throtl_destroy_tg(struct throtl_data *td, struct throtl_grp *tg)
 940 {
 941         /* Something wrong if we are trying to remove same group twice */
 942         BUG_ON(hlist_unhashed(&tg->tg_node));
 943
 944         hlist_del_init(&tg->tg_node);
 945
 946         /*
 947          * Put the reference taken at the time of creation so that when all
 948          * queues are gone, group can be destroyed.
 949          */
 950         throtl_put_tg(tg);
 951         td->nr_undestroyed_grps--;
 952 }
 953
 954 static void throtl_release_tgs(struct throtl_data *td)
 955 {
 956         struct hlist_node *pos, *n;
 957         struct throtl_grp *tg;
 958
 959         hlist_for_each_entry_safe(tg, pos, n, &td->tg_list, tg_node) {
 960                 /*
 961                  * If cgroup removal path got to blk_group first and removed
 962                  * it from cgroup list, then it will take care of destroying
 963                  * cfqg also.
 964                  */
 965                 if (!blkiocg_del_blkio_group(&tg->blkg))
 966                         throtl_destroy_tg(td, tg);
 967         }
 968 }
 969
 970 static void throtl_td_free(struct throtl_data *td)
 971 {
 972         kfree(td);
 973 }
 974
 975 /*
 976  * Blk cgroup controller notification saying that blkio_group object is being
 977  * delinked as associated cgroup object is going away. That also means that
 978  * no new IO will come in this group. So get rid of this group as soon as
 979  * any pending IO in the group is finished.
 980  *
 981  * This function is called under rcu_read_lock(). key is the rcu protected
 982  * pointer. That means "key" is a valid throtl_data pointer as long as we are
 983  * rcu read lock.
 984  *
 985  * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
 986  * it should not be NULL as even if queue was going away, cgroup deltion
 987  * path got to it first.
 988  */
 989 void throtl_unlink_blkio_group(void *key, struct blkio_group *blkg)
 990 {
 991         unsigned long flags;
 992         struct throtl_data *td = key;
 993
 994         spin_lock_irqsave(td->queue->queue_lock, flags);
 995         throtl_destroy_tg(td, tg_of_blkg(blkg));
 996         spin_unlock_irqrestore(td->queue->queue_lock, flags);
 997 }
 998
 999 static void throtl_update_blkio_group_common(struct throtl_data *td,
1000                                 struct throtl_grp *tg)
1001 {
1002         xchg(&tg->limits_changed, true);
1003         xchg(&td->limits_changed, true);
1004         /* Schedule a work now to process the limit change */
1005         throtl_schedule_delayed_work(td, 0);
1006 }
1007
1008 /*
1009  * For all update functions, key should be a valid pointer because these
1010  * update functions are called under blkcg_lock, that means, blkg is
1011  * valid and in turn key is valid. queue exit path can not race because
1012  * of blkcg_lock
1013  *
1014  * Can not take queue lock in update functions as queue lock under blkcg_lock
1015  * is not allowed. Under other paths we take blkcg_lock under queue_lock.
1016  */
1017 static void throtl_update_blkio_group_read_bps(void *key,
1018                                 struct blkio_group *blkg, u64 read_bps)
1019 {
1020         struct throtl_data *td = key;
1021         struct throtl_grp *tg = tg_of_blkg(blkg);
1022
1023         tg->bps[READ] = read_bps;
1024         throtl_update_blkio_group_common(td, tg);
1025 }
1026
1027 static void throtl_update_blkio_group_write_bps(void *key,
1028                                 struct blkio_group *blkg, u64 write_bps)
1029 {
1030         struct throtl_data *td = key;
1031         struct throtl_grp *tg = tg_of_blkg(blkg);
1032
1033         tg->bps[WRITE] = write_bps;
1034         throtl_update_blkio_group_common(td, tg);
1035 }
1036
1037 static void throtl_update_blkio_group_read_iops(void *key,
1038                         struct blkio_group *blkg, unsigned int read_iops)
1039 {
1040         struct throtl_data *td = key;
1041         struct throtl_grp *tg = tg_of_blkg(blkg);
1042
1043         tg->iops[READ] = read_iops;
1044         throtl_update_blkio_group_common(td, tg);
1045 }
1046
1047 static void throtl_update_blkio_group_write_iops(void *key,
1048                         struct blkio_group *blkg, unsigned int write_iops)
1049 {
1050         struct throtl_data *td = key;
1051         struct throtl_grp *tg = tg_of_blkg(blkg);
1052
1053         tg->iops[WRITE] = write_iops;
1054         throtl_update_blkio_group_common(td, tg);
1055 }
1056
1057 static void throtl_shutdown_wq(struct request_queue *q)
1058 {
1059         struct throtl_data *td = q->td;
1060
1061         cancel_delayed_work_sync(&td->throtl_work);
1062 }
1063
1064 static struct blkio_policy_type blkio_policy_throtl = {
1065         .ops = {
1066                 .blkio_unlink_group_fn = throtl_unlink_blkio_group,
1067                 .blkio_update_group_read_bps_fn =
1068                                         throtl_update_blkio_group_read_bps,
1069                 .blkio_update_group_write_bps_fn =
1070                                         throtl_update_blkio_group_write_bps,
1071                 .blkio_update_group_read_iops_fn =
1072                                         throtl_update_blkio_group_read_iops,
1073                 .blkio_update_group_write_iops_fn =
1074                                         throtl_update_blkio_group_write_iops,
1075         },
1076         .plid = BLKIO_POLICY_THROTL,
1077 };
1078
1079 int blk_throtl_bio(struct request_queue *q, struct bio **biop)
1080 {
1081         struct throtl_data *td = q->td;
1082         struct throtl_grp *tg;
1083         struct bio *bio = *biop;
1084         bool rw = bio_data_dir(bio), update_disptime = true;
1085
1086         if (bio->bi_rw & REQ_THROTTLED) {
1087                 bio->bi_rw &= ~REQ_THROTTLED;
1088                 return 0;
1089         }
1090
1091         spin_lock_irq(q->queue_lock);
1092         tg = throtl_get_tg(td);
1093
1094         if (IS_ERR(tg)) {
1095                 if (PTR_ERR(tg) == -ENODEV) {
1096                         /*
1097                          * Queue is gone. No queue lock held here.
1098                          */
1099                         return -ENODEV;
1100                 }
1101         }
1102
1103         if (tg->nr_queued[rw]) {
1104                 /*
1105                  * There is already another bio queued in same dir. No
1106                  * need to update dispatch time.
1107                  */
1108                 update_disptime = false;
1109                 goto queue_bio;
1110
1111         }
1112
1113         /* Bio is with-in rate limit of group */
1114         if (tg_may_dispatch(td, tg, bio, NULL)) {
1115                 throtl_charge_bio(tg, bio);
1116
1117                 /*
1118                  * We need to trim slice even when bios are not being queued
1119                  * otherwise it might happen that a bio is not queued for
1120                  * a long time and slice keeps on extending and trim is not
1121                  * called for a long time. Now if limits are reduced suddenly
1122                  * we take into account all the IO dispatched so far at new
1123                  * low rate and * newly queued IO gets a really long dispatch
1124                  * time.
1125                  *
1126                  * So keep on trimming slice even if bio is not queued.
1127                  */
1128                 throtl_trim_slice(td, tg, rw);
1129                 goto out;
1130         }
1131
1132 queue_bio:
1133         throtl_log_tg(td, tg, "[%c] bio. bdisp=%u sz=%u bps=%llu"
1134                         " iodisp=%u iops=%u queued=%d/%d",
1135                         rw == READ ? 'R' : 'W',
1136                         tg->bytes_disp[rw], bio->bi_size, tg->bps[rw],
1137                         tg->io_disp[rw], tg->iops[rw],
1138                         tg->nr_queued[READ], tg->nr_queued[WRITE]);
1139
1140         throtl_add_bio_tg(q->td, tg, bio);
1141         *biop = NULL;
1142
1143         if (update_disptime) {
1144                 tg_update_disptime(td, tg);
1145                 throtl_schedule_next_dispatch(td);
1146         }
1147
1148 out:
1149         spin_unlock_irq(q->queue_lock);
1150         return 0;
1151 }
1152
1153 int blk_throtl_init(struct request_queue *q)
1154 {
1155         struct throtl_data *td;
1156         struct throtl_grp *tg;
1157
1158         td = kzalloc_node(sizeof(*td), GFP_KERNEL, q->node);
1159         if (!td)
1160                 return -ENOMEM;
1161
1162         INIT_HLIST_HEAD(&td->tg_list);
1163         td->tg_service_tree = THROTL_RB_ROOT;
1164         td->limits_changed = false;
1165         INIT_DELAYED_WORK(&td->throtl_work, blk_throtl_work);
1166
1167         /* alloc and Init root group. */
1168         td->queue = q;
1169         tg = throtl_alloc_tg(td);
1170
1171         if (!tg) {
1172                 kfree(td);
1173                 return -ENOMEM;
1174         }
1175
1176         td->root_tg = tg;
1177
1178         rcu_read_lock();
1179         throtl_init_add_tg_lists(td, tg, &blkio_root_cgroup);
1180         rcu_read_unlock();
1181
1182         /* Attach throtl data to request queue */
1183         q->td = td;
1184         return 0;
1185 }
1186
1187 void blk_throtl_exit(struct request_queue *q)
1188 {
1189         struct throtl_data *td = q->td;
1190         bool wait = false;
1191
1192         BUG_ON(!td);
1193
1194         throtl_shutdown_wq(q);
1195
1196         spin_lock_irq(q->queue_lock);
1197         throtl_release_tgs(td);
1198
1199         /* If there are other groups */
1200         if (td->nr_undestroyed_grps > 0)
1201                 wait = true;
1202
1203         spin_unlock_irq(q->queue_lock);
1204
1205         /*
1206          * Wait for tg->blkg->key accessors to exit their grace periods.
1207          * Do this wait only if there are other undestroyed groups out
1208          * there (other than root group). This can happen if cgroup deletion
1209          * path claimed the responsibility of cleaning up a group before
1210          * queue cleanup code get to the group.
1211          *
1212          * Do not call synchronize_rcu() unconditionally as there are drivers
1213          * which create/delete request queue hundreds of times during scan/boot
1214          * and synchronize_rcu() can take significant time and slow down boot.
1215          */
1216         if (wait)
1217                 synchronize_rcu();
1218
1219         /*
1220          * Just being safe to make sure after previous flush if some body did
1221          * update limits through cgroup and another work got queued, cancel
1222          * it.
1223          */
1224         throtl_shutdown_wq(q);
1225         throtl_td_free(td);
1226 }
1227
1228 static int __init throtl_init(void)
1229 {
1230         kthrotld_workqueue = alloc_workqueue("kthrotld", WQ_MEM_RECLAIM, 0);
1231         if (!kthrotld_workqueue)
1232                 panic("Failed to create kthrotld\n");
1233
1234         blkio_policy_register(&blkio_policy_throtl);
1235         return 0;
1236 }
1237
1238 module_init(throtl_init);