block/blk-throttle.c

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