Re: [PATCH v4 1/2] blk-throttle: simplify logic by token bucket algorithm

[Vivek Goyal]

On Thu, Apr 10, 2014 at 06:07:05PM +0800, Hong zhi guo wrote:
> Hi, Tejun, Vivek and Jens,
> 
> I did tests and you affirmed the idea, and Vivek said he'll review the
> last version of the patch. But it seems he left blkio area more than
> half year. What next should I do to make progress ?

Hong,

I would say post the patches again with your testing information. I will
review these.

Thanks
Vivek

> 
> BRs
> Zhiguo
> 
> On Sun, Oct 20, 2013 at 8:11 PM, Hong Zhiguo <honkiko@xxxxxxxxx> wrote:
> > Token bucket algorithm(http://en.wikipedia.org/wiki/Token_bucket)
> > is very simple and widely used for rate limiting and shaping.
> > It's well suitable for blk-throttle. And it naturally works for
> > hierarchical cgroups. So I took it to replace the original time
> > _slicing_|_trimming_|_extending_ logic.
> >
> > The advantage is simplicity, reliability and less fluctuation.
> >
> > About 300 lines of code for time-slicing is replaced with 60 lines
> > of code for token bucket in blk-throttle.c.
> >
> > I've tested this patch by fio with rw=randread, rw=randrw. It
> > behaves almost the same with original time-slicing implementation,
> > and with less fluctuation. It's also tested on hierarchical setup.
> >
> > Signed-off-by: Hong Zhiguo <zhiguohong@xxxxxxxxxxx>
> > Tested-by: Hong Zhiguo <zhiguohong@xxxxxxxxxxx>
> > ---
> >  block/blk-throttle.c | 285 +++++++++------------------------------------------
> >  1 file changed, 50 insertions(+), 235 deletions(-)
> >
> > diff --git a/block/blk-throttle.c b/block/blk-throttle.c
> > index 8331aba..45d4d91 100644
> > --- a/block/blk-throttle.c
> > +++ b/block/blk-throttle.c
> > @@ -2,6 +2,8 @@
> >   * Interface for controlling IO bandwidth on a request queue
> >   *
> >   * Copyright (C) 2010 Vivek Goyal <vgoyal@xxxxxxxxxx>
> > + *
> > + * Simplify the logic with token bucket, Hong Zhiguo <zhiguohong@xxxxxxxxxxx>
> >   */
> >
> >  #include <linux/module.h>
> > @@ -18,9 +20,6 @@ static int throtl_grp_quantum = 8;
> >  /* Total max dispatch from all groups in one round */
> >  static int throtl_quantum = 32;
> >
> > -/* Throttling is performed over 100ms slice and after that slice is renewed */
> > -static unsigned long throtl_slice = HZ/10;     /* 100 ms */
> > -
> >  static struct blkcg_policy blkcg_policy_throtl;
> >
> >  /* A workqueue to queue throttle related work */
> > @@ -91,6 +90,11 @@ struct tg_stats_cpu {
> >         struct blkg_rwstat              serviced;
> >  };
> >
> > +/* Depth of iops token bucket */
> > +#define THROTL_BURST_IO 8
> > +/* Depth of bps token bucket */
> > +#define THROTL_BURST_BYTES (4096 * 8)
> > +
> >  struct throtl_grp {
> >         /* must be the first member */
> >         struct blkg_policy_data pd;
> > @@ -133,14 +137,13 @@ struct throtl_grp {
> >         /* IOPS limits */
> >         unsigned int iops[2];
> >
> > -       /* Number of bytes disptached in current slice */
> > -       uint64_t bytes_disp[2];
> > -       /* Number of bio's dispatched in current slice */
> > -       unsigned int io_disp[2];
> > +       /* Token for throttling by bps */
> > +       uint64_t bytes_token[2];
> > +       /* Token for throttling by iops */
> > +       unsigned int io_token[2];
> >
> > -       /* When did we start a new slice */
> > -       unsigned long slice_start[2];
> > -       unsigned long slice_end[2];
> > +       /* Time check-point */
> > +       unsigned long t_c[2];
> >
> >         /* Per cpu stats pointer */
> >         struct tg_stats_cpu __percpu *stats_cpu;
> > @@ -680,171 +683,39 @@ static bool throtl_schedule_next_dispatch(struct throtl_service_queue *sq,
> >         return false;
> >  }
> >
> > -static inline void throtl_start_new_slice_with_credit(struct throtl_grp *tg,
> > -               bool rw, unsigned long start)
> > -{
> > -       tg->bytes_disp[rw] = 0;
> > -       tg->io_disp[rw] = 0;
> > -
> > -       /*
> > -        * Previous slice has expired. We must have trimmed it after last
> > -        * bio dispatch. That means since start of last slice, we never used
> > -        * that bandwidth. Do try to make use of that bandwidth while giving
> > -        * credit.
> > -        */
> > -       if (time_after_eq(start, tg->slice_start[rw]))
> > -               tg->slice_start[rw] = start;
> > -
> > -       tg->slice_end[rw] = jiffies + throtl_slice;
> > -       throtl_log(&tg->service_queue,
> > -                  "[%c] new slice with credit start=%lu end=%lu jiffies=%lu",
> > -                  rw == READ ? 'R' : 'W', tg->slice_start[rw],
> > -                  tg->slice_end[rw], jiffies);
> > -}
> > -
> > -static inline void throtl_start_new_slice(struct throtl_grp *tg, bool rw)
> > -{
> > -       tg->bytes_disp[rw] = 0;
> > -       tg->io_disp[rw] = 0;
> > -       tg->slice_start[rw] = jiffies;
> > -       tg->slice_end[rw] = jiffies + throtl_slice;
> > -       throtl_log(&tg->service_queue,
> > -                  "[%c] new slice start=%lu end=%lu jiffies=%lu",
> > -                  rw == READ ? 'R' : 'W', tg->slice_start[rw],
> > -                  tg->slice_end[rw], jiffies);
> > -}
> > -
> > -static inline void throtl_set_slice_end(struct throtl_grp *tg, bool rw,
> > -                                       unsigned long jiffy_end)
> > -{
> > -       tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
> > -}
> > -
> > -static inline void throtl_extend_slice(struct throtl_grp *tg, bool rw,
> > -                                      unsigned long jiffy_end)
> > -{
> > -       tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
> > -       throtl_log(&tg->service_queue,
> > -                  "[%c] extend slice start=%lu end=%lu jiffies=%lu",
> > -                  rw == READ ? 'R' : 'W', tg->slice_start[rw],
> > -                  tg->slice_end[rw], jiffies);
> > -}
> > -
> > -/* Determine if previously allocated or extended slice is complete or not */
> > -static bool throtl_slice_used(struct throtl_grp *tg, bool rw)
> > -{
> > -       if (time_in_range(jiffies, tg->slice_start[rw], tg->slice_end[rw]))
> > -               return 0;
> > -
> > -       return 1;
> > -}
> > -
> > -/* Trim the used slices and adjust slice start accordingly */
> > -static inline void throtl_trim_slice(struct throtl_grp *tg, bool rw)
> > +static void tg_update_token(struct throtl_grp *tg, bool rw)
> >  {
> > -       unsigned long nr_slices, time_elapsed, io_trim;
> > -       u64 bytes_trim, tmp;
> > +       unsigned long tdiff = jiffies - tg->t_c[rw];
> > +       u64 token;
> >
> > -       BUG_ON(time_before(tg->slice_end[rw], tg->slice_start[rw]));
> > -
> > -       /*
> > -        * If bps are unlimited (-1), then time slice don't get
> > -        * renewed. Don't try to trim the slice if slice is used. A new
> > -        * slice will start when appropriate.
> > -        */
> > -       if (throtl_slice_used(tg, rw))
> > +       if (!tdiff)
> >                 return;
> >
> > -       /*
> > -        * A bio has been dispatched. Also adjust slice_end. It might happen
> > -        * that initially cgroup limit was very low resulting in high
> > -        * slice_end, but later limit was bumped up and bio was dispached
> > -        * sooner, then we need to reduce slice_end. A high bogus slice_end
> > -        * is bad because it does not allow new slice to start.
> > -        */
> > +       token = (u64)tg->iops[rw] * tdiff;
> > +       do_div(token, HZ);
> > +       tg->io_token[rw] += token;
> >
> > -       throtl_set_slice_end(tg, rw, jiffies + throtl_slice);
> > +       token = (u64)tg->bps[rw] * tdiff;
> > +       do_div(token, HZ);
> > +       tg->bytes_token[rw] += token;
> >
> > -       time_elapsed = jiffies - tg->slice_start[rw];
> > -
> > -       nr_slices = time_elapsed / throtl_slice;
> > -
> > -       if (!nr_slices)
> > -               return;
> > -       tmp = tg->bps[rw] * throtl_slice * nr_slices;
> > -       do_div(tmp, HZ);
> > -       bytes_trim = tmp;
> > -
> > -       io_trim = (tg->iops[rw] * throtl_slice * nr_slices)/HZ;
> > -
> > -       if (!bytes_trim && !io_trim)
> > -               return;
> > -
> > -       if (tg->bytes_disp[rw] >= bytes_trim)
> > -               tg->bytes_disp[rw] -= bytes_trim;
> > -       else
> > -               tg->bytes_disp[rw] = 0;
> > -
> > -       if (tg->io_disp[rw] >= io_trim)
> > -               tg->io_disp[rw] -= io_trim;
> > -       else
> > -               tg->io_disp[rw] = 0;
> > -
> > -       tg->slice_start[rw] += nr_slices * throtl_slice;
> > -
> > -       throtl_log(&tg->service_queue,
> > -                  "[%c] trim slice nr=%lu bytes=%llu io=%lu start=%lu end=%lu jiffies=%lu",
> > -                  rw == READ ? 'R' : 'W', nr_slices, bytes_trim, io_trim,
> > -                  tg->slice_start[rw], tg->slice_end[rw], jiffies);
> > +       tg->t_c[rw] = jiffies;
> >  }
> >
> >  static bool tg_with_in_iops_limit(struct throtl_grp *tg, struct bio *bio,
> >                                   unsigned long *wait)
> >  {
> >         bool rw = bio_data_dir(bio);
> > -       unsigned int io_allowed;
> > -       unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
> > -       u64 tmp;
> > -
> > -       jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
> > -
> > -       /* Slice has just started. Consider one slice interval */
> > -       if (!jiffy_elapsed)
> > -               jiffy_elapsed_rnd = throtl_slice;
> > -
> > -       jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
> >
> > -       /*
> > -        * jiffy_elapsed_rnd should not be a big value as minimum iops can be
> > -        * 1 then at max jiffy elapsed should be equivalent of 1 second as we
> > -        * will allow dispatch after 1 second and after that slice should
> > -        * have been trimmed.
> > -        */
> > -
> > -       tmp = (u64)tg->iops[rw] * jiffy_elapsed_rnd;
> > -       do_div(tmp, HZ);
> > -
> > -       if (tmp > UINT_MAX)
> > -               io_allowed = UINT_MAX;
> > -       else
> > -               io_allowed = tmp;
> > -
> > -       if (tg->io_disp[rw] + 1 <= io_allowed) {
> > +       if (tg->io_token[rw]) {
> >                 if (wait)
> >                         *wait = 0;
> >                 return 1;
> >         }
> >
> >         /* Calc approx time to dispatch */
> > -       jiffy_wait = ((tg->io_disp[rw] + 1) * HZ)/tg->iops[rw] + 1;
> > -
> > -       if (jiffy_wait > jiffy_elapsed)
> > -               jiffy_wait = jiffy_wait - jiffy_elapsed;
> > -       else
> > -               jiffy_wait = 1;
> > -
> >         if (wait)
> > -               *wait = jiffy_wait;
> > +               *wait = HZ / tg->iops[rw] ?: 1;
> >         return 0;
> >  }
> >
> > @@ -852,41 +723,21 @@ static bool tg_with_in_bps_limit(struct throtl_grp *tg, struct bio *bio,
> >                                  unsigned long *wait)
> >  {
> >         bool rw = bio_data_dir(bio);
> > -       u64 bytes_allowed, extra_bytes, tmp;
> > -       unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
> > -
> > -       jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
> > +       u64 extra_bytes;
> > +       unsigned long jiffy_wait;
> >
> > -       /* Slice has just started. Consider one slice interval */
> > -       if (!jiffy_elapsed)
> > -               jiffy_elapsed_rnd = throtl_slice;
> > -
> > -       jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
> > -
> > -       tmp = tg->bps[rw] * jiffy_elapsed_rnd;
> > -       do_div(tmp, HZ);
> > -       bytes_allowed = tmp;
> > -
> > -       if (tg->bytes_disp[rw] + bio->bi_size <= bytes_allowed) {
> > +       if (bio->bi_size <= tg->bytes_token[rw]) {
> >                 if (wait)
> >                         *wait = 0;
> >                 return 1;
> >         }
> >
> >         /* Calc approx time to dispatch */
> > -       extra_bytes = tg->bytes_disp[rw] + bio->bi_size - bytes_allowed;
> > -       jiffy_wait = div64_u64(extra_bytes * HZ, tg->bps[rw]);
> > -
> > -       if (!jiffy_wait)
> > -               jiffy_wait = 1;
> > -
> > -       /*
> > -        * This wait time is without taking into consideration the rounding
> > -        * up we did. Add that time also.
> > -        */
> > -       jiffy_wait = jiffy_wait + (jiffy_elapsed_rnd - jiffy_elapsed);
> > -       if (wait)
> > -               *wait = jiffy_wait;
> > +       if (wait) {
> > +               extra_bytes = bio->bi_size - tg->bytes_token[rw];
> > +               jiffy_wait = div64_u64(extra_bytes * HZ, tg->bps[rw]);
> > +               *wait = jiffy_wait ?: 1;
> > +       }
> >         return 0;
> >  }
> >
> > @@ -916,18 +767,7 @@ static bool tg_may_dispatch(struct throtl_grp *tg, struct bio *bio,
> >                 return 1;
> >         }
> >
> > -       /*
> > -        * If previous slice expired, start a new one otherwise renew/extend
> > -        * existing slice to make sure it is at least throtl_slice interval
> > -        * long since now.
> > -        */
> > -       if (throtl_slice_used(tg, rw))
> > -               throtl_start_new_slice(tg, rw);
> > -       else {
> > -               if (time_before(tg->slice_end[rw], jiffies + throtl_slice))
> > -                       throtl_extend_slice(tg, rw, jiffies + throtl_slice);
> > -       }
> > -
> > +       tg_update_token(tg, rw);
> >         if (tg_with_in_bps_limit(tg, bio, &bps_wait) &&
> >             tg_with_in_iops_limit(tg, bio, &iops_wait)) {
> >                 if (wait)
> > @@ -940,9 +780,6 @@ static bool tg_may_dispatch(struct throtl_grp *tg, struct bio *bio,
> >         if (wait)
> >                 *wait = max_wait;
> >
> > -       if (time_before(tg->slice_end[rw], jiffies + max_wait))
> > -               throtl_extend_slice(tg, rw, jiffies + max_wait);
> > -
> >         return 0;
> >  }
> >
> > @@ -976,9 +813,16 @@ static void throtl_charge_bio(struct throtl_grp *tg, struct bio *bio)
> >  {
> >         bool rw = bio_data_dir(bio);
> >
> > -       /* Charge the bio to the group */
> > -       tg->bytes_disp[rw] += bio->bi_size;
> > -       tg->io_disp[rw]++;
> > +       tg_update_token(tg, rw);
> > +
> > +       /* Charge the bio to the group and trim the bucket */
> > +       tg->bytes_token[rw] -= bio->bi_size;
> > +       if (tg->bytes_token[rw] > THROTL_BURST_BYTES)
> > +               tg->bytes_token[rw] = THROTL_BURST_BYTES;
> > +
> > +       tg->io_token[rw]--;
> > +       if (tg->io_token[rw] > THROTL_BURST_IO)
> > +               tg->io_token[rw] = THROTL_BURST_IO;
> >
> >         /*
> >          * REQ_THROTTLED is used to prevent the same bio to be throttled
> > @@ -1055,16 +899,6 @@ static void tg_update_disptime(struct throtl_grp *tg)
> >         tg->flags &= ~THROTL_TG_WAS_EMPTY;
> >  }
> >
> > -static void start_parent_slice_with_credit(struct throtl_grp *child_tg,
> > -                                       struct throtl_grp *parent_tg, bool rw)
> > -{
> > -       if (throtl_slice_used(parent_tg, rw)) {
> > -               throtl_start_new_slice_with_credit(parent_tg, rw,
> > -                               child_tg->slice_start[rw]);
> > -       }
> > -
> > -}
> > -
> >  static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
> >  {
> >         struct throtl_service_queue *sq = &tg->service_queue;
> > @@ -1093,7 +927,6 @@ static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
> >          */
> >         if (parent_tg) {
> >                 throtl_add_bio_tg(bio, &tg->qnode_on_parent[rw], parent_tg);
> > -               start_parent_slice_with_credit(tg, parent_tg, rw);
> >         } else {
> >                 throtl_qnode_add_bio(bio, &tg->qnode_on_parent[rw],
> >                                      &parent_sq->queued[rw]);
> > @@ -1101,8 +934,6 @@ static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
> >                 tg->td->nr_queued[rw]--;
> >         }
> >
> > -       throtl_trim_slice(tg, rw);
> > -
> >         if (tg_to_put)
> >                 blkg_put(tg_to_blkg(tg_to_put));
> >  }
> > @@ -1386,12 +1217,8 @@ static int tg_set_conf(struct cgroup_subsys_state *css, struct cftype *cft,
> >          * We're already holding queue_lock and know @tg is valid.  Let's
> >          * apply the new config directly.
> >          *
> > -        * Restart the slices for both READ and WRITES. It might happen
> > -        * that a group's limit are dropped suddenly and we don't want to
> > -        * account recently dispatched IO with new low rate.
> > +        * Update dispatch time.
> >          */
> > -       throtl_start_new_slice(tg, 0);
> > -       throtl_start_new_slice(tg, 1);
> >
> >         if (tg->flags & THROTL_TG_PENDING) {
> >                 tg_update_disptime(tg);
> > @@ -1527,19 +1354,6 @@ bool blk_throtl_bio(struct request_queue *q, struct bio *bio)
> >                 throtl_charge_bio(tg, bio);
> >
> >                 /*
> > -                * We need to trim slice even when bios are not being queued
> > -                * otherwise it might happen that a bio is not queued for
> > -                * a long time and slice keeps on extending and trim is not
> > -                * called for a long time. Now if limits are reduced suddenly
> > -                * we take into account all the IO dispatched so far at new
> > -                * low rate and * newly queued IO gets a really long dispatch
> > -                * time.
> > -                *
> > -                * So keep on trimming slice even if bio is not queued.
> > -                */
> > -               throtl_trim_slice(tg, rw);
> > -
> > -               /*
> >                  * @bio passed through this layer without being throttled.
> >                  * Climb up the ladder.  If we''re already at the top, it
> >                  * can be executed directly.
> > @@ -1552,10 +1366,11 @@ bool blk_throtl_bio(struct request_queue *q, struct bio *bio)
> >         }
> >
> >         /* out-of-limit, queue to @tg */
> > -       throtl_log(sq, "[%c] bio. bdisp=%llu sz=%u bps=%llu iodisp=%u iops=%u queued=%d/%d",
> > +       throtl_log(sq,
> > +                  "[%c] btk=%llu sz=%u bps=%llu iotk=%u iops=%u queued=%d/%d",
> >                    rw == READ ? 'R' : 'W',
> > -                  tg->bytes_disp[rw], bio->bi_size, tg->bps[rw],
> > -                  tg->io_disp[rw], tg->iops[rw],
> > +                  tg->bytes_token[rw], bio->bi_size, tg->bps[rw],
> > +                  tg->io_token[rw], tg->iops[rw],
> >                    sq->nr_queued[READ], sq->nr_queued[WRITE]);
> >
> >         bio_associate_current(bio);
> > --
> > 1.8.1.2
> >
> 
> 
> 
> -- 
> best regards
> Hong Zhiguo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/