lkml.org 
[lkml]   [2011]   [Nov]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [PATCH 02/18] writeback: dirty position control
    From
    Hello Fengguang,

    Is this the similar idea&algo behind TCP congestion control
    since 2.6.19 ?

    Same situation: Multiple tcp connections contending for network
    bandwidth V.S. multiple process contending for BDI bandwidth.

    Same solution: Per connection(v.s. process) speed control with cubic
    algorithm controlled balancing.

    :-)

    Then the validness and efficiency in essence has been verified
    in real world for years in another similar situation. Good to see we
    are going to have it in write-back too!


    Thanks,
    Nai


    On Sun, Sep 4, 2011 at 9:53 AM, Wu Fengguang <fengguang.wu@intel.com> wrote:
    > bdi_position_ratio() provides a scale factor to bdi->dirty_ratelimit, so
    > that the resulted task rate limit can drive the dirty pages back to the
    > global/bdi setpoints.
    >
    > Old scheme is,
    >                                          |
    >                           free run area  |  throttle area
    >  ----------------------------------------+---------------------------->
    >                                    thresh^                  dirty pages
    >
    > New scheme is,
    >
    >  ^ task rate limit
    >  |
    >  |            *
    >  |             *
    >  |              *
    >  |[free run]      *      [smooth throttled]
    >  |                  *
    >  |                     *
    >  |                         *
    >  ..bdi->dirty_ratelimit..........*
    >  |                               .     *
    >  |                               .          *
    >  |                               .              *
    >  |                               .                 *
    >  |                               .                    *
    >  +-------------------------------.-----------------------*------------>
    >                          setpoint^                  limit^  dirty pages
    >
    > The slope of the bdi control line should be
    >
    > 1) large enough to pull the dirty pages to setpoint reasonably fast
    >
    > 2) small enough to avoid big fluctuations in the resulted pos_ratio and
    >   hence task ratelimit
    >
    > Since the fluctuation range of the bdi dirty pages is typically observed
    > to be within 1-second worth of data, the bdi control line's slope is
    > selected to be a linear function of bdi write bandwidth, so that it can
    > adapt to slow/fast storage devices well.
    >
    > Assume the bdi control line
    >
    >        pos_ratio = 1.0 + k * (dirty - bdi_setpoint)
    >
    > where k is the negative slope.
    >
    > If targeting for 12.5% fluctuation range in pos_ratio when dirty pages
    > are fluctuating in range
    >
    >        [bdi_setpoint - write_bw/2, bdi_setpoint + write_bw/2],
    >
    > we get slope
    >
    >        k = - 1 / (8 * write_bw)
    >
    > Let pos_ratio(x_intercept) = 0, we get the parameter used in code:
    >
    >        x_intercept = bdi_setpoint + 8 * write_bw
    >
    > The global/bdi slopes are nicely complementing each other when the
    > system has only one major bdi (indicated by bdi_thresh ~= thresh):
    >
    > 1) slope of global control line    => scaling to the control scope size
    > 2) slope of main bdi control line  => scaling to the writeout bandwidth
    >
    > so that
    >
    > - in memory tight systems, (1) becomes strong enough to squeeze dirty
    >  pages inside the control scope
    >
    > - in large memory systems where the "gravity" of (1) for pulling the
    >  dirty pages to setpoint is too weak, (2) can back (1) up and drive
    >  dirty pages to bdi_setpoint ~= setpoint reasonably fast.
    >
    > Unfortunately in JBOD setups, the fluctuation range of bdi threshold
    > is related to memory size due to the interferences between disks.  In
    > this case, the bdi slope will be weighted sum of write_bw and bdi_thresh.
    >
    > Given equations
    >
    >        span = x_intercept - bdi_setpoint
    >        k = df/dx = - 1 / span
    >
    > and the extremum values
    >
    >        span = bdi_thresh
    >        dx = bdi_thresh
    >
    > we get
    >
    >        df = - dx / span = - 1.0
    >
    > That means, when bdi_dirty deviates bdi_thresh up, pos_ratio and hence
    > task ratelimit will fluctuate by -100%.
    >
    > peter: use 3rd order polynomial for the global control line
    >
    > CC: Peter Zijlstra <a.p.zijlstra@chello.nl>
    > Acked-by: Jan Kara <jack@suse.cz>
    > Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
    > ---
    >  fs/fs-writeback.c         |    2
    >  include/linux/writeback.h |    1
    >  mm/page-writeback.c       |  213 +++++++++++++++++++++++++++++++++++-
    >  3 files changed, 210 insertions(+), 6 deletions(-)
    >
    > --- linux-next.orig/mm/page-writeback.c 2011-08-26 15:57:18.000000000 +0800
    > +++ linux-next/mm/page-writeback.c      2011-08-26 15:57:34.000000000 +0800
    > @@ -46,6 +46,8 @@
    >  */
    >  #define BANDWIDTH_INTERVAL     max(HZ/5, 1)
    >
    > +#define RATELIMIT_CALC_SHIFT   10
    > +
    >  /*
    >  * After a CPU has dirtied this many pages, balance_dirty_pages_ratelimited
    >  * will look to see if it needs to force writeback or throttling.
    > @@ -409,6 +411,12 @@ int bdi_set_max_ratio(struct backing_dev
    >  }
    >  EXPORT_SYMBOL(bdi_set_max_ratio);
    >
    > +static unsigned long dirty_freerun_ceiling(unsigned long thresh,
    > +                                          unsigned long bg_thresh)
    > +{
    > +       return (thresh + bg_thresh) / 2;
    > +}
    > +
    >  static unsigned long hard_dirty_limit(unsigned long thresh)
    >  {
    >        return max(thresh, global_dirty_limit);
    > @@ -493,6 +501,197 @@ unsigned long bdi_dirty_limit(struct bac
    >        return bdi_dirty;
    >  }
    >
    > +/*
    > + * Dirty position control.
    > + *
    > + * (o) global/bdi setpoints
    > + *
    > + * We want the dirty pages be balanced around the global/bdi setpoints.
    > + * When the number of dirty pages is higher/lower than the setpoint, the
    > + * dirty position control ratio (and hence task dirty ratelimit) will be
    > + * decreased/increased to bring the dirty pages back to the setpoint.
    > + *
    > + *     pos_ratio = 1 << RATELIMIT_CALC_SHIFT
    > + *
    > + *     if (dirty < setpoint) scale up   pos_ratio
    > + *     if (dirty > setpoint) scale down pos_ratio
    > + *
    > + *     if (bdi_dirty < bdi_setpoint) scale up   pos_ratio
    > + *     if (bdi_dirty > bdi_setpoint) scale down pos_ratio
    > + *
    > + *     task_ratelimit = dirty_ratelimit * pos_ratio >> RATELIMIT_CALC_SHIFT
    > + *
    > + * (o) global control line
    > + *
    > + *     ^ pos_ratio
    > + *     |
    > + *     |            |<===== global dirty control scope ======>|
    > + * 2.0 .............*
    > + *     |            .*
    > + *     |            . *
    > + *     |            .   *
    > + *     |            .     *
    > + *     |            .        *
    > + *     |            .            *
    > + * 1.0 ................................*
    > + *     |            .                  .     *
    > + *     |            .                  .          *
    > + *     |            .                  .              *
    > + *     |            .                  .                 *
    > + *     |            .                  .                    *
    > + *   0 +------------.------------------.----------------------*------------->
    > + *           freerun^          setpoint^                 limit^   dirty pages
    > + *
    > + * (o) bdi control lines
    > + *
    > + * The control lines for the global/bdi setpoints both stretch up to @limit.
    > + * The below figure illustrates the main bdi control line with an auxiliary
    > + * line extending it to @limit.
    > + *
    > + *   o
    > + *     o
    > + *       o                                      [o] main control line
    > + *         o                                    [*] auxiliary control line
    > + *           o
    > + *             o
    > + *               o
    > + *                 o
    > + *                   o
    > + *                     o
    > + *                       o--------------------- balance point, rate scale = 1
    > + *                       | o
    > + *                       |   o
    > + *                       |     o
    > + *                       |       o
    > + *                       |         o
    > + *                       |           o
    > + *                       |             o------- connect point, rate scale = 1/2
    > + *                       |               .*
    > + *                       |                 .   *
    > + *                       |                   .      *
    > + *                       |                     .         *
    > + *                       |                       .           *
    > + *                       |                         .              *
    > + *                       |                           .                 *
    > + *  [--------------------+-----------------------------.--------------------*]
    > + *  0              bdi_setpoint                    x_intercept           limit
    > + *
    > + * The auxiliary control line allows smoothly throttling bdi_dirty down to
    > + * normal if it starts high in situations like
    > + * - start writing to a slow SD card and a fast disk at the same time. The SD
    > + *   card's bdi_dirty may rush to many times higher than bdi_setpoint.
    > + * - the bdi dirty thresh drops quickly due to change of JBOD workload
    > + */
    > +static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
    > +                                       unsigned long thresh,
    > +                                       unsigned long bg_thresh,
    > +                                       unsigned long dirty,
    > +                                       unsigned long bdi_thresh,
    > +                                       unsigned long bdi_dirty)
    > +{
    > +       unsigned long write_bw = bdi->avg_write_bandwidth;
    > +       unsigned long freerun = dirty_freerun_ceiling(thresh, bg_thresh);
    > +       unsigned long limit = hard_dirty_limit(thresh);
    > +       unsigned long x_intercept;
    > +       unsigned long setpoint;         /* dirty pages' target balance point */
    > +       unsigned long bdi_setpoint;
    > +       unsigned long span;
    > +       long long pos_ratio;            /* for scaling up/down the rate limit */
    > +       long x;
    > +
    > +       if (unlikely(dirty >= limit))
    > +               return 0;
    > +
    > +       /*
    > +        * global setpoint
    > +        *
    > +        *                           setpoint - dirty 3
    > +        *        f(dirty) := 1.0 + (----------------)
    > +        *                           limit - setpoint
    > +        *
    > +        * it's a 3rd order polynomial that subjects to
    > +        *
    > +        * (1) f(freerun)  = 2.0 => rampup dirty_ratelimit reasonably fast
    > +        * (2) f(setpoint) = 1.0 => the balance point
    > +        * (3) f(limit)    = 0   => the hard limit
    > +        * (4) df/dx      <= 0   => negative feedback control
    > +        * (5) the closer to setpoint, the smaller |df/dx| (and the reverse)
    > +        *     => fast response on large errors; small oscillation near setpoint
    > +        */
    > +       setpoint = (freerun + limit) / 2;
    > +       x = div_s64((setpoint - dirty) << RATELIMIT_CALC_SHIFT,
    > +                   limit - setpoint + 1);
    > +       pos_ratio = x;
    > +       pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
    > +       pos_ratio = pos_ratio * x >> RATELIMIT_CALC_SHIFT;
    > +       pos_ratio += 1 << RATELIMIT_CALC_SHIFT;
    > +
    > +       /*
    > +        * We have computed basic pos_ratio above based on global situation. If
    > +        * the bdi is over/under its share of dirty pages, we want to scale
    > +        * pos_ratio further down/up. That is done by the following mechanism.
    > +        */
    > +
    > +       /*
    > +        * bdi setpoint
    > +        *
    > +        *        f(bdi_dirty) := 1.0 + k * (bdi_dirty - bdi_setpoint)
    > +        *
    > +        *                        x_intercept - bdi_dirty
    > +        *                     := --------------------------
    > +        *                        x_intercept - bdi_setpoint
    > +        *
    > +        * The main bdi control line is a linear function that subjects to
    > +        *
    > +        * (1) f(bdi_setpoint) = 1.0
    > +        * (2) k = - 1 / (8 * write_bw)  (in single bdi case)
    > +        *     or equally: x_intercept = bdi_setpoint + 8 * write_bw
    > +        *
    > +        * For single bdi case, the dirty pages are observed to fluctuate
    > +        * regularly within range
    > +        *        [bdi_setpoint - write_bw/2, bdi_setpoint + write_bw/2]
    > +        * for various filesystems, where (2) can yield in a reasonable 12.5%
    > +        * fluctuation range for pos_ratio.
    > +        *
    > +        * For JBOD case, bdi_thresh (not bdi_dirty!) could fluctuate up to its
    > +        * own size, so move the slope over accordingly and choose a slope that
    > +        * yields 100% pos_ratio fluctuation on suddenly doubled bdi_thresh.
    > +        */
    > +       if (unlikely(bdi_thresh > thresh))
    > +               bdi_thresh = thresh;
    > +       /*
    > +        * scale global setpoint to bdi's:
    > +        *      bdi_setpoint = setpoint * bdi_thresh / thresh
    > +        */
    > +       x = div_u64((u64)bdi_thresh << 16, thresh + 1);
    > +       bdi_setpoint = setpoint * (u64)x >> 16;
    > +       /*
    > +        * Use span=(8*write_bw) in single bdi case as indicated by
    > +        * (thresh - bdi_thresh ~= 0) and transit to bdi_thresh in JBOD case.
    > +        *
    > +        *        bdi_thresh                    thresh - bdi_thresh
    > +        * span = ---------- * (8 * write_bw) + ------------------- * bdi_thresh
    > +        *          thresh                            thresh
    > +        */
    > +       span = (thresh - bdi_thresh + 8 * write_bw) * (u64)x >> 16;
    > +       x_intercept = bdi_setpoint + span;
    > +
    > +       span >>= 1;
    > +       if (unlikely(bdi_dirty > bdi_setpoint + span)) {
    > +               if (unlikely(bdi_dirty > limit))
    > +                       return 0;
    > +               if (x_intercept < limit) {
    > +                       x_intercept = limit;    /* auxiliary control line */
    > +                       bdi_setpoint += span;
    > +                       pos_ratio >>= 1;
    > +               }
    > +       }
    > +       pos_ratio *= x_intercept - bdi_dirty;
    > +       do_div(pos_ratio, x_intercept - bdi_setpoint + 1);
    > +
    > +       return pos_ratio;
    > +}
    > +
    >  static void bdi_update_write_bandwidth(struct backing_dev_info *bdi,
    >                                       unsigned long elapsed,
    >                                       unsigned long written)
    > @@ -591,6 +790,7 @@ static void global_update_bandwidth(unsi
    >
    >  void __bdi_update_bandwidth(struct backing_dev_info *bdi,
    >                            unsigned long thresh,
    > +                           unsigned long bg_thresh,
    >                            unsigned long dirty,
    >                            unsigned long bdi_thresh,
    >                            unsigned long bdi_dirty,
    > @@ -627,6 +827,7 @@ snapshot:
    >
    >  static void bdi_update_bandwidth(struct backing_dev_info *bdi,
    >                                 unsigned long thresh,
    > +                                unsigned long bg_thresh,
    >                                 unsigned long dirty,
    >                                 unsigned long bdi_thresh,
    >                                 unsigned long bdi_dirty,
    > @@ -635,8 +836,8 @@ static void bdi_update_bandwidth(struct
    >        if (time_is_after_eq_jiffies(bdi->bw_time_stamp + BANDWIDTH_INTERVAL))
    >                return;
    >        spin_lock(&bdi->wb.list_lock);
    > -       __bdi_update_bandwidth(bdi, thresh, dirty, bdi_thresh, bdi_dirty,
    > -                              start_time);
    > +       __bdi_update_bandwidth(bdi, thresh, bg_thresh, dirty,
    > +                              bdi_thresh, bdi_dirty, start_time);
    >        spin_unlock(&bdi->wb.list_lock);
    >  }
    >
    > @@ -677,7 +878,8 @@ static void balance_dirty_pages(struct a
    >                 * catch-up. This avoids (excessively) small writeouts
    >                 * when the bdi limits are ramping up.
    >                 */
    > -               if (nr_dirty <= (background_thresh + dirty_thresh) / 2)
    > +               if (nr_dirty <= dirty_freerun_ceiling(dirty_thresh,
    > +                                                     background_thresh))
    >                        break;
    >
    >                bdi_thresh = bdi_dirty_limit(bdi, dirty_thresh);
    > @@ -721,8 +923,9 @@ static void balance_dirty_pages(struct a
    >                if (!bdi->dirty_exceeded)
    >                        bdi->dirty_exceeded = 1;
    >
    > -               bdi_update_bandwidth(bdi, dirty_thresh, nr_dirty,
    > -                                    bdi_thresh, bdi_dirty, start_time);
    > +               bdi_update_bandwidth(bdi, dirty_thresh, background_thresh,
    > +                                    nr_dirty, bdi_thresh, bdi_dirty,
    > +                                    start_time);
    >
    >                /* Note: nr_reclaimable denotes nr_dirty + nr_unstable.
    >                 * Unstable writes are a feature of certain networked
    > --- linux-next.orig/fs/fs-writeback.c   2011-08-26 15:57:18.000000000 +0800
    > +++ linux-next/fs/fs-writeback.c        2011-08-26 15:57:20.000000000 +0800
    > @@ -675,7 +675,7 @@ static inline bool over_bground_thresh(v
    >  static void wb_update_bandwidth(struct bdi_writeback *wb,
    >                                unsigned long start_time)
    >  {
    > -       __bdi_update_bandwidth(wb->bdi, 0, 0, 0, 0, start_time);
    > +       __bdi_update_bandwidth(wb->bdi, 0, 0, 0, 0, 0, start_time);
    >  }
    >
    >  /*
    > --- linux-next.orig/include/linux/writeback.h   2011-08-26 15:57:18.000000000 +0800
    > +++ linux-next/include/linux/writeback.h        2011-08-26 15:57:20.000000000 +0800
    > @@ -141,6 +141,7 @@ unsigned long bdi_dirty_limit(struct bac
    >
    >  void __bdi_update_bandwidth(struct backing_dev_info *bdi,
    >                            unsigned long thresh,
    > +                           unsigned long bg_thresh,
    >                            unsigned long dirty,
    >                            unsigned long bdi_thresh,
    >                            unsigned long bdi_dirty,
    >
    >
    > --
    > To unsubscribe, send a message with 'unsubscribe linux-mm' in
    > the body to majordomo@kvack.org.  For more info on Linux MM,
    > see: http://www.linux-mm.org/ .
    > Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
    > Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
    >
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2011-11-12 06:47    [W:0.058 / U:61.672 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site