Quelle  blk-iocost.c   Sprache: C

/* SPDX-License-Identifier: GPL-2.0
 *
 * IO cost model based controller.
 *
 * Copyright (C) 2019 Tejun Heo <tj@kernel.org>
 * Copyright (C) 2019 Andy Newell <newella@fb.com>
 * Copyright (C) 2019 Facebook
 *
 * One challenge of controlling IO resources is the lack of trivially
 * observable cost metric.  This is distinguished from CPU and memory where
 * wallclock time and the number of bytes can serve as accurate enough
 * approximations.
 *
 * Bandwidth and iops are the most commonly used metrics for IO devices but
 * depending on the type and specifics of the device, different IO patterns
 * easily lead to multiple orders of magnitude variations rendering them
 * useless for the purpose of IO capacity distribution.  While on-device
 * time, with a lot of clutches, could serve as a useful approximation for
 * non-queued rotational devices, this is no longer viable with modern
 * devices, even the rotational ones.
 *
 * While there is no cost metric we can trivially observe, it isn't a
 * complete mystery.  For example, on a rotational device, seek cost
 * dominates while a contiguous transfer contributes a smaller amount
 * proportional to the size.  If we can characterize at least the relative
 * costs of these different types of IOs, it should be possible to
 * implement a reasonable work-conserving proportional IO resource
 * distribution.
 *
 * 1. IO Cost Model
 *
 * IO cost model estimates the cost of an IO given its basic parameters and
 * history (e.g. the end sector of the last IO).  The cost is measured in
 * device time.  If a given IO is estimated to cost 10ms, the device should
 * be able to process ~100 of those IOs in a second.
 *
 * Currently, there's only one builtin cost model - linear.  Each IO is
 * classified as sequential or random and given a base cost accordingly.
 * On top of that, a size cost proportional to the length of the IO is
 * added.  While simple, this model captures the operational
 * characteristics of a wide varienty of devices well enough.  Default
 * parameters for several different classes of devices are provided and the
 * parameters can be configured from userspace via
 * /sys/fs/cgroup/io.cost.model.
 *
 * If needed, tools/cgroup/iocost_coef_gen.py can be used to generate
 * device-specific coefficients.
 *
 * 2. Control Strategy
 *
 * The device virtual time (vtime) is used as the primary control metric.
 * The control strategy is composed of the following three parts.
 *
 * 2-1. Vtime Distribution
 *
 * When a cgroup becomes active in terms of IOs, its hierarchical share is
 * calculated.  Please consider the following hierarchy where the numbers
 * inside parentheses denote the configured weights.
 *
 *           root
 *         /       \
 *      A (w:100)  B (w:300)
 *      /       \
 *  A0 (w:100)  A1 (w:100)
 *
 * If B is idle and only A0 and A1 are actively issuing IOs, as the two are
 * of equal weight, each gets 50% share.  If then B starts issuing IOs, B
 * gets 300/(100+300) or 75% share, and A0 and A1 equally splits the rest,
 * 12.5% each.  The distribution mechanism only cares about these flattened
 * shares.  They're called hweights (hierarchical weights) and always add
 * upto 1 (WEIGHT_ONE).
 *
 * A given cgroup's vtime runs slower in inverse proportion to its hweight.
 * For example, with 12.5% weight, A0's time runs 8 times slower (100/12.5)
 * against the device vtime - an IO which takes 10ms on the underlying
 * device is considered to take 80ms on A0.
 *
 * This constitutes the basis of IO capacity distribution.  Each cgroup's
 * vtime is running at a rate determined by its hweight.  A cgroup tracks
 * the vtime consumed by past IOs and can issue a new IO if doing so
 * wouldn't outrun the current device vtime.  Otherwise, the IO is
 * suspended until the vtime has progressed enough to cover it.
 *
 * 2-2. Vrate Adjustment
 *
 * It's unrealistic to expect the cost model to be perfect.  There are too
 * many devices and even on the same device the overall performance
 * fluctuates depending on numerous factors such as IO mixture and device
 * internal garbage collection.  The controller needs to adapt dynamically.
 *
 * This is achieved by adjusting the overall IO rate according to how busy
 * the device is.  If the device becomes overloaded, we're sending down too
 * many IOs and should generally slow down.  If there are waiting issuers
 * but the device isn't saturated, we're issuing too few and should
 * generally speed up.
 *
 * To slow down, we lower the vrate - the rate at which the device vtime
 * passes compared to the wall clock.  For example, if the vtime is running
 * at the vrate of 75%, all cgroups added up would only be able to issue
 * 750ms worth of IOs per second, and vice-versa for speeding up.
 *
 * Device business is determined using two criteria - rq wait and
 * completion latencies.
 *
 * When a device gets saturated, the on-device and then the request queues
 * fill up and a bio which is ready to be issued has to wait for a request
 * to become available.  When this delay becomes noticeable, it's a clear
 * indication that the device is saturated and we lower the vrate.  This
 * saturation signal is fairly conservative as it only triggers when both
 * hardware and software queues are filled up, and is used as the default
 * busy signal.
 *
 * As devices can have deep queues and be unfair in how the queued commands
 * are executed, solely depending on rq wait may not result in satisfactory
 * control quality.  For a better control quality, completion latency QoS
 * parameters can be configured so that the device is considered saturated
 * if N'th percentile completion latency rises above the set point.
 *
 * The completion latency requirements are a function of both the
 * underlying device characteristics and the desired IO latency quality of
 * service.  There is an inherent trade-off - the tighter the latency QoS,
 * the higher the bandwidth lossage.  Latency QoS is disabled by default
 * and can be set through /sys/fs/cgroup/io.cost.qos.
 *
 * 2-3. Work Conservation
 *
 * Imagine two cgroups A and B with equal weights.  A is issuing a small IO
 * periodically while B is sending out enough parallel IOs to saturate the
 * device on its own.  Let's say A's usage amounts to 100ms worth of IO
 * cost per second, i.e., 10% of the device capacity.  The naive
 * distribution of half and half would lead to 60% utilization of the
 * device, a significant reduction in the total amount of work done
 * compared to free-for-all competition.  This is too high a cost to pay
 * for IO control.
 *
 * To conserve the total amount of work done, we keep track of how much
 * each active cgroup is actually using and yield part of its weight if
 * there are other cgroups which can make use of it.  In the above case,
 * A's weight will be lowered so that it hovers above the actual usage and
 * B would be able to use the rest.
 *
 * As we don't want to penalize a cgroup for donating its weight, the
 * surplus weight adjustment factors in a margin and has an immediate
 * snapback mechanism in case the cgroup needs more IO vtime for itself.
 *
 * Note that adjusting down surplus weights has the same effects as
 * accelerating vtime for other cgroups and work conservation can also be
 * implemented by adjusting vrate dynamically.  However, squaring who can
 * donate and should take back how much requires hweight propagations
 * anyway making it easier to implement and understand as a separate
 * mechanism.
 *
 * 3. Monitoring
 *
 * Instead of debugfs or other clumsy monitoring mechanisms, this
 * controller uses a drgn based monitoring script -
 * tools/cgroup/iocost_monitor.py.  For details on drgn, please see
 * https://github.com/osandov/drgn.  The output looks like the following.
 *
 *  sdb RUN   per=300ms cur_per=234.218:v203.695 busy= +1 vrate= 62.12%
 *                 active      weight      hweight% inflt% dbt  delay usages%
 *  test/a              *    50/   50  33.33/ 33.33  27.65   2  0*041 033:033:033
 *  test/b              *   100/  100  66.67/ 66.67  17.56   0  0*000 066:079:077
 *
 * - per : Timer period
 * - cur_per : Internal wall and device vtime clock
 * - vrate : Device virtual time rate against wall clock
 * - weight : Surplus-adjusted and configured weights
 * - hweight : Surplus-adjusted and configured hierarchical weights
 * - inflt : The percentage of in-flight IO cost at the end of last period
 * - del_ms : Deferred issuer delay induction level and duration
 * - usages : Usage history
 */

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timer.h>
#include <linux/time64.h>
#include <linux/parser.h>
#include <linux/sched/signal.h>
#include <asm/local.h>
#include <asm/local64.h>
#include "blk-rq-qos.h"
#include "blk-stat.h"
#include "blk-wbt.h"
#include "blk-cgroup.h"

#ifdef CONFIG_TRACEPOINTS

/* copied from TRACE_CGROUP_PATH, see cgroup-internal.h */
#define TRACE_IOCG_PATH_LEN 1024
static DEFINE_SPINLOCK(trace_iocg_path_lock);
static char trace_iocg_path[TRACE_IOCG_PATH_LEN];

#define TRACE_IOCG_PATH(type, iocg, ...)     \
 do {         \
  unsigned long flags;      \
  if (trace_iocost_##type##_enabled()) {    \
   spin_lock_irqsave(&trace_iocg_path_lock, flags); \
   cgroup_path(iocg_to_blkg(iocg)->blkcg->css.cgroup, \
        trace_iocg_path, TRACE_IOCG_PATH_LEN); \
   trace_iocost_##type(iocg, trace_iocg_path,  \
           ##__VA_ARGS__);   \
   spin_unlock_irqrestore(&trace_iocg_path_lock, flags); \
  }        \
 } while (0)

#else /* CONFIG_TRACE_POINTS */
#define TRACE_IOCG_PATH(type, iocg, ...) do { } while (0)
#endif /* CONFIG_TRACE_POINTS */

enum {
 MILLION   = 1000000,

 /* timer period is calculated from latency requirements, bound it */
 MIN_PERIOD  = USEC_PER_MSEC,
 MAX_PERIOD  = USEC_PER_SEC,

 /*
 * iocg->vtime is targeted at 50% behind the device vtime, which
 * serves as its IO credit buffer.  Surplus weight adjustment is
 * immediately canceled if the vtime margin runs below 10%.
 */
 MARGIN_MIN_PCT  = 10,
 MARGIN_LOW_PCT  = 20,
 MARGIN_TARGET_PCT = 50,

 INUSE_ADJ_STEP_PCT = 25,

 /* Have some play in timer operations */
 TIMER_SLACK_PCT  = 1,

 /* 1/64k is granular enough and can easily be handled w/ u32 */
 WEIGHT_ONE  = 1 << 16,
};

enum {
 /*
 * As vtime is used to calculate the cost of each IO, it needs to
 * be fairly high precision.  For example, it should be able to
 * represent the cost of a single page worth of discard with
 * suffificient accuracy.  At the same time, it should be able to
 * represent reasonably long enough durations to be useful and
 * convenient during operation.
 *
 * 1s worth of vtime is 2^37.  This gives us both sub-nanosecond
 * granularity and days of wrap-around time even at extreme vrates.
 */
 VTIME_PER_SEC_SHIFT = 37,
 VTIME_PER_SEC  = 1LLU << VTIME_PER_SEC_SHIFT,
 VTIME_PER_USEC  = VTIME_PER_SEC / USEC_PER_SEC,
 VTIME_PER_NSEC  = VTIME_PER_SEC / NSEC_PER_SEC,

 /* bound vrate adjustments within two orders of magnitude */
 VRATE_MIN_PPM  = 10000, /* 1% */
 VRATE_MAX_PPM  = 100000000, /* 10000% */

 VRATE_MIN  = VTIME_PER_USEC * VRATE_MIN_PPM / MILLION,
 VRATE_CLAMP_ADJ_PCT = 4,

 /* switch iff the conditions are met for longer than this */
 AUTOP_CYCLE_NSEC = 10LLU * NSEC_PER_SEC,
};

enum {
 /* if IOs end up waiting for requests, issue less */
 RQ_WAIT_BUSY_PCT = 5,

 /* unbusy hysterisis */
 UNBUSY_THR_PCT  = 75,

 /*
 * The effect of delay is indirect and non-linear and a huge amount of
 * future debt can accumulate abruptly while unthrottled. Linearly scale
 * up delay as debt is going up and then let it decay exponentially.
 * This gives us quick ramp ups while delay is accumulating and long
 * tails which can help reducing the frequency of debt explosions on
 * unthrottle. The parameters are experimentally determined.
 *
 * The delay mechanism provides adequate protection and behavior in many
 * cases. However, this is far from ideal and falls shorts on both
 * fronts. The debtors are often throttled too harshly costing a
 * significant level of fairness and possibly total work while the
 * protection against their impacts on the system can be choppy and
 * unreliable.
 *
 * The shortcoming primarily stems from the fact that, unlike for page
 * cache, the kernel doesn't have well-defined back-pressure propagation
 * mechanism and policies for anonymous memory. Fully addressing this
 * issue will likely require substantial improvements in the area.
 */
 MIN_DELAY_THR_PCT = 500,
 MAX_DELAY_THR_PCT = 25000,
 MIN_DELAY  = 250,
 MAX_DELAY  = 250 * USEC_PER_MSEC,

 /* halve debts if avg usage over 100ms is under 50% */
 DFGV_USAGE_PCT  = 50,
 DFGV_PERIOD  = 100 * USEC_PER_MSEC,

 /* don't let cmds which take a very long time pin lagging for too long */
 MAX_LAGGING_PERIODS = 10,

 /*
 * Count IO size in 4k pages.  The 12bit shift helps keeping
 * size-proportional components of cost calculation in closer
 * numbers of digits to per-IO cost components.
 */
 IOC_PAGE_SHIFT  = 12,
 IOC_PAGE_SIZE  = 1 << IOC_PAGE_SHIFT,
 IOC_SECT_TO_PAGE_SHIFT = IOC_PAGE_SHIFT - SECTOR_SHIFT,

 /* if apart further than 16M, consider randio for linear model */
 LCOEF_RANDIO_PAGES = 4096,
};

enum ioc_running {
 IOC_IDLE,
 IOC_RUNNING,
 IOC_STOP,
};

/* io.cost.qos controls including per-dev enable of the whole controller */
enum {
 QOS_ENABLE,
 QOS_CTRL,
 NR_QOS_CTRL_PARAMS,
};

/* io.cost.qos params */
enum {
 QOS_RPPM,
 QOS_RLAT,
 QOS_WPPM,
 QOS_WLAT,
 QOS_MIN,
 QOS_MAX,
 NR_QOS_PARAMS,
};

/* io.cost.model controls */
enum {
 COST_CTRL,
 COST_MODEL,
 NR_COST_CTRL_PARAMS,
};

/* builtin linear cost model coefficients */
enum {
 I_LCOEF_RBPS,
 I_LCOEF_RSEQIOPS,
 I_LCOEF_RRANDIOPS,
 I_LCOEF_WBPS,
 I_LCOEF_WSEQIOPS,
 I_LCOEF_WRANDIOPS,
 NR_I_LCOEFS,
};

enum {
 LCOEF_RPAGE,
 LCOEF_RSEQIO,
 LCOEF_RRANDIO,
 LCOEF_WPAGE,
 LCOEF_WSEQIO,
 LCOEF_WRANDIO,
 NR_LCOEFS,
};

enum {
 AUTOP_INVALID,
 AUTOP_HDD,
 AUTOP_SSD_QD1,
 AUTOP_SSD_DFL,
 AUTOP_SSD_FAST,
};

struct ioc_params {
 u32    qos[NR_QOS_PARAMS];
 u64    i_lcoefs[NR_I_LCOEFS];
 u64    lcoefs[NR_LCOEFS];
 u32    too_fast_vrate_pct;
 u32    too_slow_vrate_pct;
};

struct ioc_margins {
 s64    min;
 s64    low;
 s64    target;
};

struct ioc_missed {
 local_t    nr_met;
 local_t    nr_missed;
 u32    last_met;
 u32    last_missed;
};

struct ioc_pcpu_stat {
 struct ioc_missed  missed[2];

 local64_t   rq_wait_ns;
 u64    last_rq_wait_ns;
};

/* per device */
struct ioc {
 struct rq_qos   rqos;

 bool    enabled;

 struct ioc_params  params;
 struct ioc_margins  margins;
 u32    period_us;
 u32    timer_slack_ns;
 u64    vrate_min;
 u64    vrate_max;

 spinlock_t   lock;
 struct timer_list  timer;
 struct list_head  active_iocgs; /* active cgroups */
 struct ioc_pcpu_stat __percpu *pcpu_stat;

 enum ioc_running  running;
 atomic64_t   vtime_rate;
 u64    vtime_base_rate;
 s64    vtime_err;

 seqcount_spinlock_t  period_seqcount;
 u64    period_at; /* wallclock starttime */
 u64    period_at_vtime; /* vtime starttime */

 atomic64_t   cur_period; /* inc'd each period */
 int    busy_level; /* saturation history */

 bool    weights_updated;
 atomic_t   hweight_gen; /* for lazy hweights */

 /* debt forgivness */
 u64    dfgv_period_at;
 u64    dfgv_period_rem;
 u64    dfgv_usage_us_sum;

 u64    autop_too_fast_at;
 u64    autop_too_slow_at;
 int    autop_idx;
 bool    user_qos_params:1;
 bool    user_cost_model:1;
};

struct iocg_pcpu_stat {
 local64_t   abs_vusage;
};

struct iocg_stat {
 u64    usage_us;
 u64    wait_us;
 u64    indebt_us;
 u64    indelay_us;
};

/* per device-cgroup pair */
struct ioc_gq {
 struct blkg_policy_data  pd;
 struct ioc   *ioc;

 /*
 * A iocg can get its weight from two sources - an explicit
 * per-device-cgroup configuration or the default weight of the
 * cgroup.  `cfg_weight` is the explicit per-device-cgroup
 * configuration.  `weight` is the effective considering both
 * sources.
 *
 * When an idle cgroup becomes active its `active` goes from 0 to
 * `weight`.  `inuse` is the surplus adjusted active weight.
 * `active` and `inuse` are used to calculate `hweight_active` and
 * `hweight_inuse`.
 *
 * `last_inuse` remembers `inuse` while an iocg is idle to persist
 * surplus adjustments.
 *
 * `inuse` may be adjusted dynamically during period. `saved_*` are used
 * to determine and track adjustments.
 */
 u32    cfg_weight;
 u32    weight;
 u32    active;
 u32    inuse;

 u32    last_inuse;
 s64    saved_margin;

 sector_t   cursor;  /* to detect randio */

 /*
 * `vtime` is this iocg's vtime cursor which progresses as IOs are
 * issued.  If lagging behind device vtime, the delta represents
 * the currently available IO budget.  If running ahead, the
 * overage.
 *
 * `vtime_done` is the same but progressed on completion rather
 * than issue.  The delta behind `vtime` represents the cost of
 * currently in-flight IOs.
 */
 atomic64_t   vtime;
 atomic64_t   done_vtime;
 u64    abs_vdebt;

 /* current delay in effect and when it started */
 u64    delay;
 u64    delay_at;

 /*
 * The period this iocg was last active in.  Used for deactivation
 * and invalidating `vtime`.
 */
 atomic64_t   active_period;
 struct list_head  active_list;

 /* see __propagate_weights() and current_hweight() for details */
 u64    child_active_sum;
 u64    child_inuse_sum;
 u64    child_adjusted_sum;
 int    hweight_gen;
 u32    hweight_active;
 u32    hweight_inuse;
 u32    hweight_donating;
 u32    hweight_after_donation;

 struct list_head  walk_list;
 struct list_head  surplus_list;

 struct wait_queue_head  waitq;
 struct hrtimer   waitq_timer;

 /* timestamp at the latest activation */
 u64    activated_at;

 /* statistics */
 struct iocg_pcpu_stat __percpu *pcpu_stat;
 struct iocg_stat  stat;
 struct iocg_stat  last_stat;
 u64    last_stat_abs_vusage;
 u64    usage_delta_us;
 u64    wait_since;
 u64    indebt_since;
 u64    indelay_since;

 /* this iocg's depth in the hierarchy and ancestors including self */
 int    level;
 struct ioc_gq   *ancestors[];
};

/* per cgroup */
struct ioc_cgrp {
 struct blkcg_policy_data cpd;
 unsigned int   dfl_weight;
};

struct ioc_now {
 u64    now_ns;
 u64    now;
 u64    vnow;
};

struct iocg_wait {
 struct wait_queue_entry  wait;
 struct bio   *bio;
 u64    abs_cost;
 bool    committed;
};

struct iocg_wake_ctx {
 struct ioc_gq   *iocg;
 u32    hw_inuse;
 s64    vbudget;
};

static const struct ioc_params autop[] = {
 [AUTOP_HDD] = {
  .qos    = {
   [QOS_RLAT]  =        250000, /* 250ms */
   [QOS_WLAT]  =        250000,
   [QOS_MIN]  = VRATE_MIN_PPM,
   [QOS_MAX]  = VRATE_MAX_PPM,
  },
  .i_lcoefs   = {
   [I_LCOEF_RBPS]  =     174019176,
   [I_LCOEF_RSEQIOPS] =         41708,
   [I_LCOEF_RRANDIOPS] =           370,
   [I_LCOEF_WBPS]  =     178075866,
   [I_LCOEF_WSEQIOPS] =         42705,
   [I_LCOEF_WRANDIOPS] =           378,
  },
 },
 [AUTOP_SSD_QD1] = {
  .qos    = {
   [QOS_RLAT]  =         25000, /* 25ms */
   [QOS_WLAT]  =         25000,
   [QOS_MIN]  = VRATE_MIN_PPM,
   [QOS_MAX]  = VRATE_MAX_PPM,
  },
  .i_lcoefs   = {
   [I_LCOEF_RBPS]  =     245855193,
   [I_LCOEF_RSEQIOPS] =         61575,
   [I_LCOEF_RRANDIOPS] =          6946,
   [I_LCOEF_WBPS]  =     141365009,
   [I_LCOEF_WSEQIOPS] =         33716,
   [I_LCOEF_WRANDIOPS] =         26796,
  },
 },
 [AUTOP_SSD_DFL] = {
  .qos    = {
   [QOS_RLAT]  =         25000, /* 25ms */
   [QOS_WLAT]  =         25000,
   [QOS_MIN]  = VRATE_MIN_PPM,
   [QOS_MAX]  = VRATE_MAX_PPM,
  },
  .i_lcoefs   = {
   [I_LCOEF_RBPS]  =     488636629,
   [I_LCOEF_RSEQIOPS] =          8932,
   [I_LCOEF_RRANDIOPS] =          8518,
   [I_LCOEF_WBPS]  =     427891549,
   [I_LCOEF_WSEQIOPS] =         28755,
   [I_LCOEF_WRANDIOPS] =         21940,
  },
  .too_fast_vrate_pct  =           500,
 },
 [AUTOP_SSD_FAST] = {
  .qos    = {
   [QOS_RLAT]  =          5000, /* 5ms */
   [QOS_WLAT]  =          5000,
   [QOS_MIN]  = VRATE_MIN_PPM,
   [QOS_MAX]  = VRATE_MAX_PPM,
  },
  .i_lcoefs   = {
   [I_LCOEF_RBPS]  =    3102524156LLU,
   [I_LCOEF_RSEQIOPS] =        724816,
   [I_LCOEF_RRANDIOPS] =        778122,
   [I_LCOEF_WBPS]  =    1742780862LLU,
   [I_LCOEF_WSEQIOPS] =        425702,
   [I_LCOEF_WRANDIOPS] =  443193,
  },
  .too_slow_vrate_pct  =            10,
 },
};

/*
 * vrate adjust percentages indexed by ioc->busy_level.  We adjust up on
 * vtime credit shortage and down on device saturation.
 */
static const u32 vrate_adj_pct[] =
 { 0, 0, 0, 0,
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
   4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16 };

static struct blkcg_policy blkcg_policy_iocost;

/* accessors and helpers */
static struct ioc *rqos_to_ioc(struct rq_qos *rqos)
{
 return container_of(rqos, struct ioc, rqos);
}

static struct ioc *q_to_ioc(struct request_queue *q)
{
 return rqos_to_ioc(rq_qos_id(q, RQ_QOS_COST));
}

static const char __maybe_unused *ioc_name(struct ioc *ioc)
{
 struct gendisk *disk = ioc->rqos.disk;

 if (!disk)
  return "";
 return disk->disk_name;
}

static struct ioc_gq *pd_to_iocg(struct blkg_policy_data *pd)
{
 return pd ? container_of(pd, struct ioc_gq, pd) : NULL;
}

static struct ioc_gq *blkg_to_iocg(struct blkcg_gq *blkg)
{
 return pd_to_iocg(blkg_to_pd(blkg, &blkcg_policy_iocost));
}

static struct blkcg_gq *iocg_to_blkg(struct ioc_gq *iocg)
{
 return pd_to_blkg(&iocg->pd);
}

static struct ioc_cgrp *blkcg_to_iocc(struct blkcg *blkcg)
{
 return container_of(blkcg_to_cpd(blkcg, &blkcg_policy_iocost),
       struct ioc_cgrp, cpd);
}

/*
 * Scale @abs_cost to the inverse of @hw_inuse.  The lower the hierarchical
 * weight, the more expensive each IO.  Must round up.
 */
static u64 abs_cost_to_cost(u64 abs_cost, u32 hw_inuse)
{
 return DIV64_U64_ROUND_UP(abs_cost * WEIGHT_ONE, hw_inuse);
}

/*
 * The inverse of abs_cost_to_cost().  Must round up.
 */
static u64 cost_to_abs_cost(u64 cost, u32 hw_inuse)
{
 return DIV64_U64_ROUND_UP(cost * hw_inuse, WEIGHT_ONE);
}

static void iocg_commit_bio(struct ioc_gq *iocg, struct bio *bio,
       u64 abs_cost, u64 cost)
{
 struct iocg_pcpu_stat *gcs;

 bio->bi_iocost_cost = cost;
 atomic64_add(cost, &iocg->vtime);

 gcs = get_cpu_ptr(iocg->pcpu_stat);
 local64_add(abs_cost, &gcs->abs_vusage);
 put_cpu_ptr(gcs);
}

static void iocg_lock(struct ioc_gq *iocg, bool lock_ioc, unsigned long *flags)
{
 if (lock_ioc) {
  spin_lock_irqsave(&iocg->ioc->lock, *flags);
  spin_lock(&iocg->waitq.lock);
 } else {
  spin_lock_irqsave(&iocg->waitq.lock, *flags);
 }
}

static void iocg_unlock(struct ioc_gq *iocg, bool unlock_ioc, unsigned long *flags)
{
 if (unlock_ioc) {
  spin_unlock(&iocg->waitq.lock);
  spin_unlock_irqrestore(&iocg->ioc->lock, *flags);
 } else {
  spin_unlock_irqrestore(&iocg->waitq.lock, *flags);
 }
}

#define CREATE_TRACE_POINTS
#include <trace/events/iocost.h>

static void ioc_refresh_margins(struct ioc *ioc)
{
 struct ioc_margins *margins = &ioc->margins;
 u32 period_us = ioc->period_us;
 u64 vrate = ioc->vtime_base_rate;

 margins->min = (period_us * MARGIN_MIN_PCT / 100) * vrate;
 margins->low = (period_us * MARGIN_LOW_PCT / 100) * vrate;
 margins->target = (period_us * MARGIN_TARGET_PCT / 100) * vrate;
}

/* latency Qos params changed, update period_us and all the dependent params */
static void ioc_refresh_period_us(struct ioc *ioc)
{
 u32 ppm, lat, multi, period_us;

 lockdep_assert_held(&ioc->lock);

 /* pick the higher latency target */
 if (ioc->params.qos[QOS_RLAT] >= ioc->params.qos[QOS_WLAT]) {
  ppm = ioc->params.qos[QOS_RPPM];
  lat = ioc->params.qos[QOS_RLAT];
 } else {
  ppm = ioc->params.qos[QOS_WPPM];
  lat = ioc->params.qos[QOS_WLAT];
 }

 /*
 * We want the period to be long enough to contain a healthy number
 * of IOs while short enough for granular control.  Define it as a
 * multiple of the latency target.  Ideally, the multiplier should
 * be scaled according to the percentile so that it would nominally
 * contain a certain number of requests.  Let's be simpler and
 * scale it linearly so that it's 2x >= pct(90) and 10x at pct(50).
 */
 if (ppm)
  multi = max_t(u32, (MILLION - ppm) / 50000, 2);
 else
  multi = 2;
 period_us = multi * lat;
 period_us = clamp_t(u32, period_us, MIN_PERIOD, MAX_PERIOD);

 /* calculate dependent params */
 ioc->period_us = period_us;
 ioc->timer_slack_ns = div64_u64(
  (u64)period_us * NSEC_PER_USEC * TIMER_SLACK_PCT,
  100);
 ioc_refresh_margins(ioc);
}

/*
 *  ioc->rqos.disk isn't initialized when this function is called from
 *  the init path.
 */
static int ioc_autop_idx(struct ioc *ioc, struct gendisk *disk)
{
 int idx = ioc->autop_idx;
 const struct ioc_params *p = &autop[idx];
 u32 vrate_pct;
 u64 now_ns;

 /* rotational? */
 if (!blk_queue_nonrot(disk->queue))
  return AUTOP_HDD;

 /* handle SATA SSDs w/ broken NCQ */
 if (blk_queue_depth(disk->queue) == 1)
  return AUTOP_SSD_QD1;

 /* use one of the normal ssd sets */
 if (idx < AUTOP_SSD_DFL)
  return AUTOP_SSD_DFL;

 /* if user is overriding anything, maintain what was there */
 if (ioc->user_qos_params || ioc->user_cost_model)
  return idx;

 /* step up/down based on the vrate */
 vrate_pct = div64_u64(ioc->vtime_base_rate * 100, VTIME_PER_USEC);
 now_ns = blk_time_get_ns();

 if (p->too_fast_vrate_pct && p->too_fast_vrate_pct <= vrate_pct) {
  if (!ioc->autop_too_fast_at)
   ioc->autop_too_fast_at = now_ns;
  if (now_ns - ioc->autop_too_fast_at >= AUTOP_CYCLE_NSEC)
   return idx + 1;
 } else {
  ioc->autop_too_fast_at = 0;
 }

 if (p->too_slow_vrate_pct && p->too_slow_vrate_pct >= vrate_pct) {
  if (!ioc->autop_too_slow_at)
   ioc->autop_too_slow_at = now_ns;
  if (now_ns - ioc->autop_too_slow_at >= AUTOP_CYCLE_NSEC)
   return idx - 1;
 } else {
  ioc->autop_too_slow_at = 0;
 }

 return idx;
}

/*
 * Take the followings as input
 *
 *  @bps maximum sequential throughput
 *  @seqiops maximum sequential 4k iops
 *  @randiops maximum random 4k iops
 *
 * and calculate the linear model cost coefficients.
 *
 *  *@page per-page cost 1s / (@bps / 4096)
 *  *@seqio base cost of a seq IO max((1s / @seqiops) - *@page, 0)
 *  @randiops base cost of a rand IO max((1s / @randiops) - *@page, 0)
 */
static void calc_lcoefs(u64 bps, u64 seqiops, u64 randiops,
   u64 *page, u64 *seqio, u64 *randio)
{
 u64 v;

 *page = *seqio = *randio = 0;

 if (bps) {
  u64 bps_pages = DIV_ROUND_UP_ULL(bps, IOC_PAGE_SIZE);

  if (bps_pages)
   *page = DIV64_U64_ROUND_UP(VTIME_PER_SEC, bps_pages);
  else
   *page = 1;
 }

 if (seqiops) {
  v = DIV64_U64_ROUND_UP(VTIME_PER_SEC, seqiops);
  if (v > *page)
   *seqio = v - *page;
 }

 if (randiops) {
  v = DIV64_U64_ROUND_UP(VTIME_PER_SEC, randiops);
  if (v > *page)
   *randio = v - *page;
 }
}

static void ioc_refresh_lcoefs(struct ioc *ioc)
{
 u64 *u = ioc->params.i_lcoefs;
 u64 *c = ioc->params.lcoefs;

 calc_lcoefs(u[I_LCOEF_RBPS], u[I_LCOEF_RSEQIOPS], u[I_LCOEF_RRANDIOPS],
      &c[LCOEF_RPAGE], &c[LCOEF_RSEQIO], &c[LCOEF_RRANDIO]);
 calc_lcoefs(u[I_LCOEF_WBPS], u[I_LCOEF_WSEQIOPS], u[I_LCOEF_WRANDIOPS],
      &c[LCOEF_WPAGE], &c[LCOEF_WSEQIO], &c[LCOEF_WRANDIO]);
}

/*
 * struct gendisk is required as an argument because ioc->rqos.disk
 * is not properly initialized when called from the init path.
 */
static bool ioc_refresh_params_disk(struct ioc *ioc, bool force,
        struct gendisk *disk)
{
 const struct ioc_params *p;
 int idx;

 lockdep_assert_held(&ioc->lock);

 idx = ioc_autop_idx(ioc, disk);
 p = &autop[idx];

 if (idx == ioc->autop_idx && !force)
  return false;

 if (idx != ioc->autop_idx) {
  atomic64_set(&ioc->vtime_rate, VTIME_PER_USEC);
  ioc->vtime_base_rate = VTIME_PER_USEC;
 }

 ioc->autop_idx = idx;
 ioc->autop_too_fast_at = 0;
 ioc->autop_too_slow_at = 0;

 if (!ioc->user_qos_params)
  memcpy(ioc->params.qos, p->qos, sizeof(p->qos));
 if (!ioc->user_cost_model)
  memcpy(ioc->params.i_lcoefs, p->i_lcoefs, sizeof(p->i_lcoefs));

 ioc_refresh_period_us(ioc);
 ioc_refresh_lcoefs(ioc);

 ioc->vrate_min = DIV64_U64_ROUND_UP((u64)ioc->params.qos[QOS_MIN] *
         VTIME_PER_USEC, MILLION);
 ioc->vrate_max = DIV64_U64_ROUND_UP((u64)ioc->params.qos[QOS_MAX] *
         VTIME_PER_USEC, MILLION);

 return true;
}

static bool ioc_refresh_params(struct ioc *ioc, bool force)
{
 return ioc_refresh_params_disk(ioc, force, ioc->rqos.disk);
}

/*
 * When an iocg accumulates too much vtime or gets deactivated, we throw away
 * some vtime, which lowers the overall device utilization. As the exact amount
 * which is being thrown away is known, we can compensate by accelerating the
 * vrate accordingly so that the extra vtime generated in the current period
 * matches what got lost.
 */
static void ioc_refresh_vrate(struct ioc *ioc, struct ioc_now *now)
{
 s64 pleft = ioc->period_at + ioc->period_us - now->now;
 s64 vperiod = ioc->period_us * ioc->vtime_base_rate;
 s64 vcomp, vcomp_min, vcomp_max;

 lockdep_assert_held(&ioc->lock);

 /* we need some time left in this period */
 if (pleft <= 0)
  goto done;

 /*
 * Calculate how much vrate should be adjusted to offset the error.
 * Limit the amount of adjustment and deduct the adjusted amount from
 * the error.
 */
 vcomp = -div64_s64(ioc->vtime_err, pleft);
 vcomp_min = -(ioc->vtime_base_rate >> 1);
 vcomp_max = ioc->vtime_base_rate;
 vcomp = clamp(vcomp, vcomp_min, vcomp_max);

 ioc->vtime_err += vcomp * pleft;

 atomic64_set(&ioc->vtime_rate, ioc->vtime_base_rate + vcomp);
done:
 /* bound how much error can accumulate */
 ioc->vtime_err = clamp(ioc->vtime_err, -vperiod, vperiod);
}

static void ioc_adjust_base_vrate(struct ioc *ioc, u32 rq_wait_pct,
      int nr_lagging, int nr_shortages,
      int prev_busy_level, u32 *missed_ppm)
{
 u64 vrate = ioc->vtime_base_rate;
 u64 vrate_min = ioc->vrate_min, vrate_max = ioc->vrate_max;

 if (!ioc->busy_level || (ioc->busy_level < 0 && nr_lagging)) {
  if (ioc->busy_level != prev_busy_level || nr_lagging)
   trace_iocost_ioc_vrate_adj(ioc, vrate,
         missed_ppm, rq_wait_pct,
         nr_lagging, nr_shortages);

  return;
 }

 /*
 * If vrate is out of bounds, apply clamp gradually as the
 * bounds can change abruptly.  Otherwise, apply busy_level
 * based adjustment.
 */
 if (vrate < vrate_min) {
  vrate = div64_u64(vrate * (100 + VRATE_CLAMP_ADJ_PCT), 100);
  vrate = min(vrate, vrate_min);
 } else if (vrate > vrate_max) {
  vrate = div64_u64(vrate * (100 - VRATE_CLAMP_ADJ_PCT), 100);
  vrate = max(vrate, vrate_max);
 } else {
  int idx = min_t(int, abs(ioc->busy_level),
    ARRAY_SIZE(vrate_adj_pct) - 1);
  u32 adj_pct = vrate_adj_pct[idx];

  if (ioc->busy_level > 0)
   adj_pct = 100 - adj_pct;
  else
   adj_pct = 100 + adj_pct;

  vrate = clamp(DIV64_U64_ROUND_UP(vrate * adj_pct, 100),
         vrate_min, vrate_max);
 }

 trace_iocost_ioc_vrate_adj(ioc, vrate, missed_ppm, rq_wait_pct,
       nr_lagging, nr_shortages);

 ioc->vtime_base_rate = vrate;
 ioc_refresh_margins(ioc);
}

/* take a snapshot of the current [v]time and vrate */
static void ioc_now(struct ioc *ioc, struct ioc_now *now)
{
 unsigned seq;
 u64 vrate;

 now->now_ns = blk_time_get_ns();
 now->now = ktime_to_us(now->now_ns);
 vrate = atomic64_read(&ioc->vtime_rate);

 /*
 * The current vtime is
 *
 *   vtime at period start + (wallclock time since the start) * vrate
 *
 * As a consistent snapshot of `period_at_vtime` and `period_at` is
 * needed, they're seqcount protected.
 */
 do {
  seq = read_seqcount_begin(&ioc->period_seqcount);
  now->vnow = ioc->period_at_vtime +
   (now->now - ioc->period_at) * vrate;
 } while (read_seqcount_retry(&ioc->period_seqcount, seq));
}

static void ioc_start_period(struct ioc *ioc, struct ioc_now *now)
{
 WARN_ON_ONCE(ioc->running != IOC_RUNNING);

 write_seqcount_begin(&ioc->period_seqcount);
 ioc->period_at = now->now;
 ioc->period_at_vtime = now->vnow;
 write_seqcount_end(&ioc->period_seqcount);

 ioc->timer.expires = jiffies + usecs_to_jiffies(ioc->period_us);
 add_timer(&ioc->timer);
}

/*
 * Update @iocg's `active` and `inuse` to @active and @inuse, update level
 * weight sums and propagate upwards accordingly. If @save, the current margin
 * is saved to be used as reference for later inuse in-period adjustments.
 */
static void __propagate_weights(struct ioc_gq *iocg, u32 active, u32 inuse,
    bool save, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 int lvl;

 lockdep_assert_held(&ioc->lock);

 /*
 * For an active leaf node, its inuse shouldn't be zero or exceed
 * @active. An active internal node's inuse is solely determined by the
 * inuse to active ratio of its children regardless of @inuse.
 */
 if (list_empty(&iocg->active_list) && iocg->child_active_sum) {
  inuse = DIV64_U64_ROUND_UP(active * iocg->child_inuse_sum,
        iocg->child_active_sum);
 } else {
  /*
 * It may be tempting to turn this into a clamp expression with
 * a lower limit of 1 but active may be 0, which cannot be used
 * as an upper limit in that situation. This expression allows
 * active to clamp inuse unless it is 0, in which case inuse
 * becomes 1.
 */
  inuse = min(inuse, active) ?: 1;
 }

 iocg->last_inuse = iocg->inuse;
 if (save)
  iocg->saved_margin = now->vnow - atomic64_read(&iocg->vtime);

 if (active == iocg->active && inuse == iocg->inuse)
  return;

 for (lvl = iocg->level - 1; lvl >= 0; lvl--) {
  struct ioc_gq *parent = iocg->ancestors[lvl];
  struct ioc_gq *child = iocg->ancestors[lvl + 1];
  u32 parent_active = 0, parent_inuse = 0;

  /* update the level sums */
  parent->child_active_sum += (s32)(active - child->active);
  parent->child_inuse_sum += (s32)(inuse - child->inuse);
  /* apply the updates */
  child->active = active;
  child->inuse = inuse;

  /*
 * The delta between inuse and active sums indicates that
 * much of weight is being given away.  Parent's inuse
 * and active should reflect the ratio.
 */
  if (parent->child_active_sum) {
   parent_active = parent->weight;
   parent_inuse = DIV64_U64_ROUND_UP(
    parent_active * parent->child_inuse_sum,
    parent->child_active_sum);
  }

  /* do we need to keep walking up? */
  if (parent_active == parent->active &&
      parent_inuse == parent->inuse)
   break;

  active = parent_active;
  inuse = parent_inuse;
 }

 ioc->weights_updated = true;
}

static void commit_weights(struct ioc *ioc)
{
 lockdep_assert_held(&ioc->lock);

 if (ioc->weights_updated) {
  /* paired with rmb in current_hweight(), see there */
  smp_wmb();
  atomic_inc(&ioc->hweight_gen);
  ioc->weights_updated = false;
 }
}

static void propagate_weights(struct ioc_gq *iocg, u32 active, u32 inuse,
         bool save, struct ioc_now *now)
{
 __propagate_weights(iocg, active, inuse, save, now);
 commit_weights(iocg->ioc);
}

static void current_hweight(struct ioc_gq *iocg, u32 *hw_activep, u32 *hw_inusep)
{
 struct ioc *ioc = iocg->ioc;
 int lvl;
 u32 hwa, hwi;
 int ioc_gen;

 /* hot path - if uptodate, use cached */
 ioc_gen = atomic_read(&ioc->hweight_gen);
 if (ioc_gen == iocg->hweight_gen)
  goto out;

 /*
 * Paired with wmb in commit_weights(). If we saw the updated
 * hweight_gen, all the weight updates from __propagate_weights() are
 * visible too.
 *
 * We can race with weight updates during calculation and get it
 * wrong.  However, hweight_gen would have changed and a future
 * reader will recalculate and we're guaranteed to discard the
 * wrong result soon.
 */
 smp_rmb();

 hwa = hwi = WEIGHT_ONE;
 for (lvl = 0; lvl <= iocg->level - 1; lvl++) {
  struct ioc_gq *parent = iocg->ancestors[lvl];
  struct ioc_gq *child = iocg->ancestors[lvl + 1];
  u64 active_sum = READ_ONCE(parent->child_active_sum);
  u64 inuse_sum = READ_ONCE(parent->child_inuse_sum);
  u32 active = READ_ONCE(child->active);
  u32 inuse = READ_ONCE(child->inuse);

  /* we can race with deactivations and either may read as zero */
  if (!active_sum || !inuse_sum)
   continue;

  active_sum = max_t(u64, active, active_sum);
  hwa = div64_u64((u64)hwa * active, active_sum);

  inuse_sum = max_t(u64, inuse, inuse_sum);
  hwi = div64_u64((u64)hwi * inuse, inuse_sum);
 }

 iocg->hweight_active = max_t(u32, hwa, 1);
 iocg->hweight_inuse = max_t(u32, hwi, 1);
 iocg->hweight_gen = ioc_gen;
out:
 if (hw_activep)
  *hw_activep = iocg->hweight_active;
 if (hw_inusep)
  *hw_inusep = iocg->hweight_inuse;
}

/*
 * Calculate the hweight_inuse @iocg would get with max @inuse assuming all the
 * other weights stay unchanged.
 */
static u32 current_hweight_max(struct ioc_gq *iocg)
{
 u32 hwm = WEIGHT_ONE;
 u32 inuse = iocg->active;
 u64 child_inuse_sum;
 int lvl;

 lockdep_assert_held(&iocg->ioc->lock);

 for (lvl = iocg->level - 1; lvl >= 0; lvl--) {
  struct ioc_gq *parent = iocg->ancestors[lvl];
  struct ioc_gq *child = iocg->ancestors[lvl + 1];

  child_inuse_sum = parent->child_inuse_sum + inuse - child->inuse;
  hwm = div64_u64((u64)hwm * inuse, child_inuse_sum);
  inuse = DIV64_U64_ROUND_UP(parent->active * child_inuse_sum,
        parent->child_active_sum);
 }

 return max_t(u32, hwm, 1);
}

static void weight_updated(struct ioc_gq *iocg, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 struct blkcg_gq *blkg = iocg_to_blkg(iocg);
 struct ioc_cgrp *iocc = blkcg_to_iocc(blkg->blkcg);
 u32 weight;

 lockdep_assert_held(&ioc->lock);

 weight = iocg->cfg_weight ?: iocc->dfl_weight;
 if (weight != iocg->weight && iocg->active)
  propagate_weights(iocg, weight, iocg->inuse, true, now);
 iocg->weight = weight;
}

static bool iocg_activate(struct ioc_gq *iocg, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 u64 __maybe_unused last_period, cur_period;
 u64 vtime, vtarget;
 int i;

 /*
 * If seem to be already active, just update the stamp to tell the
 * timer that we're still active.  We don't mind occassional races.
 */
 if (!list_empty(&iocg->active_list)) {
  ioc_now(ioc, now);
  cur_period = atomic64_read(&ioc->cur_period);
  if (atomic64_read(&iocg->active_period) != cur_period)
   atomic64_set(&iocg->active_period, cur_period);
  return true;
 }

 /* racy check on internal node IOs, treat as root level IOs */
 if (iocg->child_active_sum)
  return false;

 spin_lock_irq(&ioc->lock);

 ioc_now(ioc, now);

 /* update period */
 cur_period = atomic64_read(&ioc->cur_period);
 last_period = atomic64_read(&iocg->active_period);
 atomic64_set(&iocg->active_period, cur_period);

 /* already activated or breaking leaf-only constraint? */
 if (!list_empty(&iocg->active_list))
  goto succeed_unlock;
 for (i = iocg->level - 1; i > 0; i--)
  if (!list_empty(&iocg->ancestors[i]->active_list))
   goto fail_unlock;

 if (iocg->child_active_sum)
  goto fail_unlock;

 /*
 * Always start with the target budget. On deactivation, we throw away
 * anything above it.
 */
 vtarget = now->vnow - ioc->margins.target;
 vtime = atomic64_read(&iocg->vtime);

 atomic64_add(vtarget - vtime, &iocg->vtime);
 atomic64_add(vtarget - vtime, &iocg->done_vtime);
 vtime = vtarget;

 /*
 * Activate, propagate weight and start period timer if not
 * running.  Reset hweight_gen to avoid accidental match from
 * wrapping.
 */
 iocg->hweight_gen = atomic_read(&ioc->hweight_gen) - 1;
 list_add(&iocg->active_list, &ioc->active_iocgs);

 propagate_weights(iocg, iocg->weight,
     iocg->last_inuse ?: iocg->weight, true, now);

 TRACE_IOCG_PATH(iocg_activate, iocg, now,
   last_period, cur_period, vtime);

 iocg->activated_at = now->now;

 if (ioc->running == IOC_IDLE) {
  ioc->running = IOC_RUNNING;
  ioc->dfgv_period_at = now->now;
  ioc->dfgv_period_rem = 0;
  ioc_start_period(ioc, now);
 }

succeed_unlock:
 spin_unlock_irq(&ioc->lock);
 return true;

fail_unlock:
 spin_unlock_irq(&ioc->lock);
 return false;
}

static bool iocg_kick_delay(struct ioc_gq *iocg, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 struct blkcg_gq *blkg = iocg_to_blkg(iocg);
 u64 tdelta, delay, new_delay, shift;
 s64 vover, vover_pct;
 u32 hwa;

 lockdep_assert_held(&iocg->waitq.lock);

 /*
 * If the delay is set by another CPU, we may be in the past. No need to
 * change anything if so. This avoids decay calculation underflow.
 */
 if (time_before64(now->now, iocg->delay_at))
  return false;

 /* calculate the current delay in effect - 1/2 every second */
 tdelta = now->now - iocg->delay_at;
 shift = div64_u64(tdelta, USEC_PER_SEC);
 if (iocg->delay && shift < BITS_PER_LONG)
  delay = iocg->delay >> shift;
 else
  delay = 0;

 /* calculate the new delay from the debt amount */
 current_hweight(iocg, &hwa, NULL);
 vover = atomic64_read(&iocg->vtime) +
  abs_cost_to_cost(iocg->abs_vdebt, hwa) - now->vnow;
 vover_pct = div64_s64(100 * vover,
         ioc->period_us * ioc->vtime_base_rate);

 if (vover_pct <= MIN_DELAY_THR_PCT)
  new_delay = 0;
 else if (vover_pct >= MAX_DELAY_THR_PCT)
  new_delay = MAX_DELAY;
 else
  new_delay = MIN_DELAY +
   div_u64((MAX_DELAY - MIN_DELAY) *
    (vover_pct - MIN_DELAY_THR_PCT),
    MAX_DELAY_THR_PCT - MIN_DELAY_THR_PCT);

 /* pick the higher one and apply */
 if (new_delay > delay) {
  iocg->delay = new_delay;
  iocg->delay_at = now->now;
  delay = new_delay;
 }

 if (delay >= MIN_DELAY) {
  if (!iocg->indelay_since)
   iocg->indelay_since = now->now;
  blkcg_set_delay(blkg, delay * NSEC_PER_USEC);
  return true;
 } else {
  if (iocg->indelay_since) {
   iocg->stat.indelay_us += now->now - iocg->indelay_since;
   iocg->indelay_since = 0;
  }
  iocg->delay = 0;
  blkcg_clear_delay(blkg);
  return false;
 }
}

static void iocg_incur_debt(struct ioc_gq *iocg, u64 abs_cost,
       struct ioc_now *now)
{
 struct iocg_pcpu_stat *gcs;

 lockdep_assert_held(&iocg->ioc->lock);
 lockdep_assert_held(&iocg->waitq.lock);
 WARN_ON_ONCE(list_empty(&iocg->active_list));

 /*
 * Once in debt, debt handling owns inuse. @iocg stays at the minimum
 * inuse donating all of it share to others until its debt is paid off.
 */
 if (!iocg->abs_vdebt && abs_cost) {
  iocg->indebt_since = now->now;
  propagate_weights(iocg, iocg->active, 0, false, now);
 }

 iocg->abs_vdebt += abs_cost;

 gcs = get_cpu_ptr(iocg->pcpu_stat);
 local64_add(abs_cost, &gcs->abs_vusage);
 put_cpu_ptr(gcs);
}

static void iocg_pay_debt(struct ioc_gq *iocg, u64 abs_vpay,
     struct ioc_now *now)
{
 lockdep_assert_held(&iocg->ioc->lock);
 lockdep_assert_held(&iocg->waitq.lock);

 /*
 * make sure that nobody messed with @iocg. Check iocg->pd.online
 * to avoid warn when removing blkcg or disk.
 */
 WARN_ON_ONCE(list_empty(&iocg->active_list) && iocg->pd.online);
 WARN_ON_ONCE(iocg->inuse > 1);

 iocg->abs_vdebt -= min(abs_vpay, iocg->abs_vdebt);

 /* if debt is paid in full, restore inuse */
 if (!iocg->abs_vdebt) {
  iocg->stat.indebt_us += now->now - iocg->indebt_since;
  iocg->indebt_since = 0;

  propagate_weights(iocg, iocg->active, iocg->last_inuse,
      false, now);
 }
}

static int iocg_wake_fn(struct wait_queue_entry *wq_entry, unsigned mode,
   int flags, void *key)
{
 struct iocg_wait *wait = container_of(wq_entry, struct iocg_wait, wait);
 struct iocg_wake_ctx *ctx = key;
 u64 cost = abs_cost_to_cost(wait->abs_cost, ctx->hw_inuse);

 ctx->vbudget -= cost;

 if (ctx->vbudget < 0)
  return -1;

 iocg_commit_bio(ctx->iocg, wait->bio, wait->abs_cost, cost);
 wait->committed = true;

 /*
 * autoremove_wake_function() removes the wait entry only when it
 * actually changed the task state. We want the wait always removed.
 * Remove explicitly and use default_wake_function(). Note that the
 * order of operations is important as finish_wait() tests whether
 * @wq_entry is removed without grabbing the lock.
 */
 default_wake_function(wq_entry, mode, flags, key);
 list_del_init_careful(&wq_entry->entry);
 return 0;
}

/*
 * Calculate the accumulated budget, pay debt if @pay_debt and wake up waiters
 * accordingly. When @pay_debt is %true, the caller must be holding ioc->lock in
 * addition to iocg->waitq.lock.
 */
static void iocg_kick_waitq(struct ioc_gq *iocg, bool pay_debt,
       struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 struct iocg_wake_ctx ctx = { .iocg = iocg };
 u64 vshortage, expires, oexpires;
 s64 vbudget;
 u32 hwa;

 lockdep_assert_held(&iocg->waitq.lock);

 current_hweight(iocg, &hwa, NULL);
 vbudget = now->vnow - atomic64_read(&iocg->vtime);

 /* pay off debt */
 if (pay_debt && iocg->abs_vdebt && vbudget > 0) {
  u64 abs_vbudget = cost_to_abs_cost(vbudget, hwa);
  u64 abs_vpay = min_t(u64, abs_vbudget, iocg->abs_vdebt);
  u64 vpay = abs_cost_to_cost(abs_vpay, hwa);

  lockdep_assert_held(&ioc->lock);

  atomic64_add(vpay, &iocg->vtime);
  atomic64_add(vpay, &iocg->done_vtime);
  iocg_pay_debt(iocg, abs_vpay, now);
  vbudget -= vpay;
 }

 if (iocg->abs_vdebt || iocg->delay)
  iocg_kick_delay(iocg, now);

 /*
 * Debt can still be outstanding if we haven't paid all yet or the
 * caller raced and called without @pay_debt. Shouldn't wake up waiters
 * under debt. Make sure @vbudget reflects the outstanding amount and is
 * not positive.
 */
 if (iocg->abs_vdebt) {
  s64 vdebt = abs_cost_to_cost(iocg->abs_vdebt, hwa);
  vbudget = min_t(s64, 0, vbudget - vdebt);
 }

 /*
 * Wake up the ones which are due and see how much vtime we'll need for
 * the next one. As paying off debt restores hw_inuse, it must be read
 * after the above debt payment.
 */
 ctx.vbudget = vbudget;
 current_hweight(iocg, NULL, &ctx.hw_inuse);

 __wake_up_locked_key(&iocg->waitq, TASK_NORMAL, &ctx);

 if (!waitqueue_active(&iocg->waitq)) {
  if (iocg->wait_since) {
   iocg->stat.wait_us += now->now - iocg->wait_since;
   iocg->wait_since = 0;
  }
  return;
 }

 if (!iocg->wait_since)
  iocg->wait_since = now->now;

 if (WARN_ON_ONCE(ctx.vbudget >= 0))
  return;

 /* determine next wakeup, add a timer margin to guarantee chunking */
 vshortage = -ctx.vbudget;
 expires = now->now_ns +
  DIV64_U64_ROUND_UP(vshortage, ioc->vtime_base_rate) *
  NSEC_PER_USEC;
 expires += ioc->timer_slack_ns;

 /* if already active and close enough, don't bother */
 oexpires = ktime_to_ns(hrtimer_get_softexpires(&iocg->waitq_timer));
 if (hrtimer_is_queued(&iocg->waitq_timer) &&
     abs(oexpires - expires) <= ioc->timer_slack_ns)
  return;

 hrtimer_start_range_ns(&iocg->waitq_timer, ns_to_ktime(expires),
          ioc->timer_slack_ns, HRTIMER_MODE_ABS);
}

static enum hrtimer_restart iocg_waitq_timer_fn(struct hrtimer *timer)
{
 struct ioc_gq *iocg = container_of(timer, struct ioc_gq, waitq_timer);
 bool pay_debt = READ_ONCE(iocg->abs_vdebt);
 struct ioc_now now;
 unsigned long flags;

 ioc_now(iocg->ioc, &now);

 iocg_lock(iocg, pay_debt, &flags);
 iocg_kick_waitq(iocg, pay_debt, &now);
 iocg_unlock(iocg, pay_debt, &flags);

 return HRTIMER_NORESTART;
}

static void ioc_lat_stat(struct ioc *ioc, u32 *missed_ppm_ar, u32 *rq_wait_pct_p)
{
 u32 nr_met[2] = { };
 u32 nr_missed[2] = { };
 u64 rq_wait_ns = 0;
 int cpu, rw;

 for_each_online_cpu(cpu) {
  struct ioc_pcpu_stat *stat = per_cpu_ptr(ioc->pcpu_stat, cpu);
  u64 this_rq_wait_ns;

  for (rw = READ; rw <= WRITE; rw++) {
   u32 this_met = local_read(&stat->missed[rw].nr_met);
   u32 this_missed = local_read(&stat->missed[rw].nr_missed);

   nr_met[rw] += this_met - stat->missed[rw].last_met;
   nr_missed[rw] += this_missed - stat->missed[rw].last_missed;
   stat->missed[rw].last_met = this_met;
   stat->missed[rw].last_missed = this_missed;
  }

  this_rq_wait_ns = local64_read(&stat->rq_wait_ns);
  rq_wait_ns += this_rq_wait_ns - stat->last_rq_wait_ns;
  stat->last_rq_wait_ns = this_rq_wait_ns;
 }

 for (rw = READ; rw <= WRITE; rw++) {
  if (nr_met[rw] + nr_missed[rw])
   missed_ppm_ar[rw] =
    DIV64_U64_ROUND_UP((u64)nr_missed[rw] * MILLION,
         nr_met[rw] + nr_missed[rw]);
  else
   missed_ppm_ar[rw] = 0;
 }

 *rq_wait_pct_p = div64_u64(rq_wait_ns * 100,
       ioc->period_us * NSEC_PER_USEC);
}

/* was iocg idle this period? */
static bool iocg_is_idle(struct ioc_gq *iocg)
{
 struct ioc *ioc = iocg->ioc;

 /* did something get issued this period? */
 if (atomic64_read(&iocg->active_period) ==
     atomic64_read(&ioc->cur_period))
  return false;

 /* is something in flight? */
 if (atomic64_read(&iocg->done_vtime) != atomic64_read(&iocg->vtime))
  return false;

 return true;
}

/*
 * Call this function on the target leaf @iocg's to build pre-order traversal
 * list of all the ancestors in @inner_walk. The inner nodes are linked through
 * ->walk_list and the caller is responsible for dissolving the list after use.
 */
static void iocg_build_inner_walk(struct ioc_gq *iocg,
      struct list_head *inner_walk)
{
 int lvl;

 WARN_ON_ONCE(!list_empty(&iocg->walk_list));

 /* find the first ancestor which hasn't been visited yet */
 for (lvl = iocg->level - 1; lvl >= 0; lvl--) {
  if (!list_empty(&iocg->ancestors[lvl]->walk_list))
   break;
 }

 /* walk down and visit the inner nodes to get pre-order traversal */
 while (++lvl <= iocg->level - 1) {
  struct ioc_gq *inner = iocg->ancestors[lvl];

  /* record traversal order */
  list_add_tail(&inner->walk_list, inner_walk);
 }
}

/* propagate the deltas to the parent */
static void iocg_flush_stat_upward(struct ioc_gq *iocg)
{
 if (iocg->level > 0) {
  struct iocg_stat *parent_stat =
   &iocg->ancestors[iocg->level - 1]->stat;

  parent_stat->usage_us +=
   iocg->stat.usage_us - iocg->last_stat.usage_us;
  parent_stat->wait_us +=
   iocg->stat.wait_us - iocg->last_stat.wait_us;
  parent_stat->indebt_us +=
   iocg->stat.indebt_us - iocg->last_stat.indebt_us;
  parent_stat->indelay_us +=
   iocg->stat.indelay_us - iocg->last_stat.indelay_us;
 }

 iocg->last_stat = iocg->stat;
}

/* collect per-cpu counters and propagate the deltas to the parent */
static void iocg_flush_stat_leaf(struct ioc_gq *iocg, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 u64 abs_vusage = 0;
 u64 vusage_delta;
 int cpu;

 lockdep_assert_held(&iocg->ioc->lock);

 /* collect per-cpu counters */
 for_each_possible_cpu(cpu) {
  abs_vusage += local64_read(
    per_cpu_ptr(&iocg->pcpu_stat->abs_vusage, cpu));
 }
 vusage_delta = abs_vusage - iocg->last_stat_abs_vusage;
 iocg->last_stat_abs_vusage = abs_vusage;

 iocg->usage_delta_us = div64_u64(vusage_delta, ioc->vtime_base_rate);
 iocg->stat.usage_us += iocg->usage_delta_us;

 iocg_flush_stat_upward(iocg);
}

/* get stat counters ready for reading on all active iocgs */
static void iocg_flush_stat(struct list_head *target_iocgs, struct ioc_now *now)
{
 LIST_HEAD(inner_walk);
 struct ioc_gq *iocg, *tiocg;

 /* flush leaves and build inner node walk list */
 list_for_each_entry(iocg, target_iocgs, active_list) {
  iocg_flush_stat_leaf(iocg, now);
  iocg_build_inner_walk(iocg, &inner_walk);
 }

 /* keep flushing upwards by walking the inner list backwards */
 list_for_each_entry_safe_reverse(iocg, tiocg, &inner_walk, walk_list) {
  iocg_flush_stat_upward(iocg);
  list_del_init(&iocg->walk_list);
 }
}

/*
 * Determine what @iocg's hweight_inuse should be after donating unused
 * capacity. @hwm is the upper bound and used to signal no donation. This
 * function also throws away @iocg's excess budget.
 */
static u32 hweight_after_donation(struct ioc_gq *iocg, u32 old_hwi, u32 hwm,
      u32 usage, struct ioc_now *now)
{
 struct ioc *ioc = iocg->ioc;
 u64 vtime = atomic64_read(&iocg->vtime);
 s64 excess, delta, target, new_hwi;

 /* debt handling owns inuse for debtors */
 if (iocg->abs_vdebt)
  return 1;

 /* see whether minimum margin requirement is met */
 if (waitqueue_active(&iocg->waitq) ||
     time_after64(vtime, now->vnow - ioc->margins.min))
  return hwm;

 /* throw away excess above target */
 excess = now->vnow - vtime - ioc->margins.target;
 if (excess > 0) {
  atomic64_add(excess, &iocg->vtime);
  atomic64_add(excess, &iocg->done_vtime);
  vtime += excess;
  ioc->vtime_err -= div64_u64(excess * old_hwi, WEIGHT_ONE);
 }

 /*
 * Let's say the distance between iocg's and device's vtimes as a
 * fraction of period duration is delta. Assuming that the iocg will
 * consume the usage determined above, we want to determine new_hwi so
 * that delta equals MARGIN_TARGET at the end of the next period.
 *
 * We need to execute usage worth of IOs while spending the sum of the
 * new budget (1 - MARGIN_TARGET) and the leftover from the last period
 * (delta):
 *
 *   usage = (1 - MARGIN_TARGET + delta) * new_hwi
 *
 * Therefore, the new_hwi is:
 *
 *   new_hwi = usage / (1 - MARGIN_TARGET + delta)
 */
 delta = div64_s64(WEIGHT_ONE * (now->vnow - vtime),
     now->vnow - ioc->period_at_vtime);
 target = WEIGHT_ONE * MARGIN_TARGET_PCT / 100;
 new_hwi = div64_s64(WEIGHT_ONE * usage, WEIGHT_ONE - target + delta);

 return clamp_t(s64, new_hwi, 1, hwm);
}

/*
 * For work-conservation, an iocg which isn't using all of its share should
 * donate the leftover to other iocgs. There are two ways to achieve this - 1.
 * bumping up vrate accordingly 2. lowering the donating iocg's inuse weight.
 *
 * #1 is mathematically simpler but has the drawback of requiring synchronous
 * global hweight_inuse updates when idle iocg's get activated or inuse weights
 * change due to donation snapbacks as it has the possibility of grossly
 * overshooting what's allowed by the model and vrate.
 *
 * #2 is inherently safe with local operations. The donating iocg can easily
 * snap back to higher weights when needed without worrying about impacts on
 * other nodes as the impacts will be inherently correct. This also makes idle
 * iocg activations safe. The only effect activations have is decreasing
 * hweight_inuse of others, the right solution to which is for those iocgs to
 * snap back to higher weights.
 *
 * So, we go with #2. The challenge is calculating how each donating iocg's
 * inuse should be adjusted to achieve the target donation amounts. This is done
 * using Andy's method described in the following pdf.
 *
 *   https://drive.google.com/file/d/1PsJwxPFtjUnwOY1QJ5AeICCcsL7BM3bo
 *
 * Given the weights and target after-donation hweight_inuse values, Andy's
 * method determines how the proportional distribution should look like at each
 * sibling level to maintain the relative relationship between all non-donating
 * pairs. To roughly summarize, it divides the tree into donating and
 * non-donating parts, calculates global donation rate which is used to
 * determine the target hweight_inuse for each node, and then derives per-level
 * proportions.
 *
 * The following pdf shows that global distribution calculated this way can be
 * achieved by scaling inuse weights of donating leaves and propagating the
 * adjustments upwards proportionally.
 *
 *   https://drive.google.com/file/d/1vONz1-fzVO7oY5DXXsLjSxEtYYQbOvsE
 *
 * Combining the above two, we can determine how each leaf iocg's inuse should
 * be adjusted to achieve the target donation.
 *
 *   https://drive.google.com/file/d/1WcrltBOSPN0qXVdBgnKm4mdp9FhuEFQN
 *
 * The inline comments use symbols from the last pdf.
 *
 *   b is the sum of the absolute budgets in the subtree. 1 for the root node.
 *   f is the sum of the absolute budgets of non-donating nodes in the subtree.
 *   t is the sum of the absolute budgets of donating nodes in the subtree.
 *   w is the weight of the node. w = w_f + w_t
 *   w_f is the non-donating portion of w. w_f = w * f / b
 *   w_b is the donating portion of w. w_t = w * t / b
 *   s is the sum of all sibling weights. s = Sum(w) for siblings
 *   s_f and s_t are the non-donating and donating portions of s.
 *
 * Subscript p denotes the parent's counterpart and ' the adjusted value - e.g.
 * w_pt is the donating portion of the parent's weight and w'_pt the same value
 * after adjustments. Subscript r denotes the root node's values.
 */
static void transfer_surpluses(struct list_head *surpluses, struct ioc_now *now)
{
 LIST_HEAD(over_hwa);
 LIST_HEAD(inner_walk);
 struct ioc_gq *iocg, *tiocg, *root_iocg;
 u32 after_sum, over_sum, over_target, gamma;

 /*
 * It's pretty unlikely but possible for the total sum of
 * hweight_after_donation's to be higher than WEIGHT_ONE, which will
 * confuse the following calculations. If such condition is detected,
 * scale down everyone over its full share equally to keep the sum below
 * WEIGHT_ONE.
 */
 after_sum = 0;
 over_sum = 0;
 list_for_each_entry(iocg, surpluses, surplus_list) {
  u32 hwa;

  current_hweight(iocg, &hwa, NULL);
  after_sum += iocg->hweight_after_donation;

  if (iocg->hweight_after_donation > hwa) {
   over_sum += iocg->hweight_after_donation;
   list_add(&iocg->walk_list, &over_hwa);
  }
 }

 if (after_sum >= WEIGHT_ONE) {
  /*
 * The delta should be deducted from the over_sum, calculate
 * target over_sum value.
 */
  u32 over_delta = after_sum - (WEIGHT_ONE - 1);
  WARN_ON_ONCE(over_sum <= over_delta);
  over_target = over_sum - over_delta;
 } else {
  over_target = 0;
 }

 list_for_each_entry_safe(iocg, tiocg, &over_hwa, walk_list) {
  if (over_target)
   iocg->hweight_after_donation =
    div_u64((u64)iocg->hweight_after_donation *
     over_target, over_sum);
  list_del_init(&iocg->walk_list);
 }

 /*
 * Build pre-order inner node walk list and prepare for donation
 * adjustment calculations.
 */
 list_for_each_entry(iocg, surpluses, surplus_list) {
  iocg_build_inner_walk(iocg, &inner_walk);
 }

 root_iocg = list_first_entry(&inner_walk, struct ioc_gq, walk_list);
 WARN_ON_ONCE(root_iocg->level > 0);

 list_for_each_entry(iocg, &inner_walk, walk_list) {
  iocg->child_adjusted_sum = 0;
  iocg->hweight_donating = 0;
  iocg->hweight_after_donation = 0;
 }

 /*
 * Propagate the donating budget (b_t) and after donation budget (b'_t)
 * up the hierarchy.
 */
 list_for_each_entry(iocg, surpluses, surplus_list) {
  struct ioc_gq *parent = iocg->ancestors[iocg->level - 1];

  parent->hweight_donating += iocg->hweight_donating;
  parent->hweight_after_donation += iocg->hweight_after_donation;
 }

 list_for_each_entry_reverse(iocg, &inner_walk, walk_list) {
  if (iocg->level > 0) {
   struct ioc_gq *parent = iocg->ancestors[iocg->level - 1];

   parent->hweight_donating += iocg->hweight_donating;
   parent->hweight_after_donation += iocg->hweight_after_donation;
  }
 }

 /*
 * Calculate inner hwa's (b) and make sure the donation values are
 * within the accepted ranges as we're doing low res calculations with
 * roundups.
 */
 list_for_each_entry(iocg, &inner_walk, walk_list) {
  if (iocg->level) {
   struct ioc_gq *parent = iocg->ancestors[iocg->level - 1];

   iocg->hweight_active = DIV64_U64_ROUND_UP(
    (u64)parent->hweight_active * iocg->active,
    parent->child_active_sum);

  }

  iocg->hweight_donating = min(iocg->hweight_donating,
          iocg->hweight_active);
  iocg->hweight_after_donation = min(iocg->hweight_after_donation,
         iocg->hweight_donating - 1);
  if (WARN_ON_ONCE(iocg->hweight_active <= 1 ||
     iocg->hweight_donating <= 1 ||
     iocg->hweight_after_donation == 0)) {
   pr_warn("iocg: invalid donation weights in ");
   pr_cont_cgroup_path(iocg_to_blkg(iocg)->blkcg->css.cgroup);
   pr_cont(": active=%u donating=%u after=%u\n",
    iocg->hweight_active, iocg->hweight_donating,
    iocg->hweight_after_donation);
  }
 }

 /*
 * Calculate the global donation rate (gamma) - the rate to adjust
 * non-donating budgets by.
 *
 * No need to use 64bit multiplication here as the first operand is
 * guaranteed to be smaller than WEIGHT_ONE (1<<16).
 *
 * We know that there are beneficiary nodes and the sum of the donating
 * hweights can't be whole; however, due to the round-ups during hweight
 * calculations, root_iocg->hweight_donating might still end up equal to
 * or greater than whole. Limit the range when calculating the divider.
 *
 * gamma = (1 - t_r') / (1 - t_r)
 */
 gamma = DIV_ROUND_UP(
  (WEIGHT_ONE - root_iocg->hweight_after_donation) * WEIGHT_ONE,
  WEIGHT_ONE - min_t(u32, root_iocg->hweight_donating, WEIGHT_ONE - 1));

 /*
 * Calculate adjusted hwi, child_adjusted_sum and inuse for the inner
 * nodes.
 */
 list_for_each_entry(iocg, &inner_walk, walk_list) {
  struct ioc_gq *parent;
  u32 inuse, wpt, wptp;
  u64 st, sf;

  if (iocg->level == 0) {
   /* adjusted weight sum for 1st level: s' = s * b_pf / b'_pf */
   iocg->child_adjusted_sum = DIV64_U64_ROUND_UP(
    iocg->child_active_sum * (WEIGHT_ONE - iocg->hweight_donating),
    WEIGHT_ONE - iocg->hweight_after_donation);
   continue;
  }

  parent = iocg->ancestors[iocg->level - 1];

  /* b' = gamma * b_f + b_t' */
  iocg->hweight_inuse = DIV64_U64_ROUND_UP(
   (u64)gamma * (iocg->hweight_active - iocg->hweight_donating),
   WEIGHT_ONE) + iocg->hweight_after_donation;

  /* w' = s' * b' / b'_p */
  inuse = DIV64_U64_ROUND_UP(
   (u64)parent->child_adjusted_sum * iocg->hweight_inuse,
   parent->hweight_inuse);

  /* adjusted weight sum for children: s' = s_f + s_t * w'_pt / w_pt */
  st = DIV64_U64_ROUND_UP(
   iocg->child_active_sum * iocg->hweight_donating,
   iocg->hweight_active);
  sf = iocg->child_active_sum - st;
  wpt = DIV64_U64_ROUND_UP(
   (u64)iocg->active * iocg->hweight_donating,
   iocg->hweight_active);
  wptp = DIV64_U64_ROUND_UP(
   (u64)inuse * iocg->hweight_after_donation,
   iocg->hweight_inuse);

  iocg->child_adjusted_sum = sf + DIV64_U64_ROUND_UP(st * wptp, wpt);
 }

 /*
 * All inner nodes now have ->hweight_inuse and ->child_adjusted_sum and
 * we can finally determine leaf adjustments.
 */
 list_for_each_entry(iocg, surpluses, surplus_list) {
  struct ioc_gq *parent = iocg->ancestors[iocg->level - 1];
  u32 inuse;

  /*
 * In-debt iocgs participated in the donation calculation with
 * the minimum target hweight_inuse. Configuring inuse
 * accordingly would work fine but debt handling expects
 * @iocg->inuse stay at the minimum and we don't wanna
 * interfere.
 */
  if (iocg->abs_vdebt) {
   WARN_ON_ONCE(iocg->inuse > 1);
   continue;
  }

  /* w' = s' * b' / b'_p, note that b' == b'_t for donating leaves */
  inuse = DIV64_U64_ROUND_UP(
   parent->child_adjusted_sum * iocg->hweight_after_donation,
   parent->hweight_inuse);

  TRACE_IOCG_PATH(inuse_transfer, iocg, now,
    iocg->inuse, inuse,
    iocg->hweight_inuse,
    iocg->hweight_after_donation);

  __propagate_weights(iocg, iocg->active, inuse, true, now);
 }

 /* walk list should be dissolved after use */
 list_for_each_entry_safe(iocg, tiocg, &inner_walk, walk_list)
  list_del_init(&iocg->walk_list);
}

/*
 * A low weight iocg can amass a large amount of debt, for example, when
 * anonymous memory gets reclaimed aggressively. If the system has a lot of
 * memory paired with a slow IO device, the debt can span multiple seconds or
 * more. If there are no other subsequent IO issuers, the in-debt iocg may end
 * up blocked paying its debt while the IO device is idle.
 *
 * The following protects against such cases. If the device has been
 * sufficiently idle for a while, the debts are halved and delays are
 * recalculated.
 */
static void ioc_forgive_debts(struct ioc *ioc, u64 usage_us_sum, int nr_debtors,
         struct ioc_now *now)
{
 struct ioc_gq *iocg;
 u64 dur, usage_pct, nr_cycles, nr_cycles_shift;

 /* if no debtor, reset the cycle */
 if (!nr_debtors) {
  ioc->dfgv_period_at = now->now;
  ioc->dfgv_period_rem = 0;
  ioc->dfgv_usage_us_sum = 0;
  return;
 }

 /*
 * Debtors can pass through a lot of writes choking the device and we
 * don't want to be forgiving debts while the device is struggling from
 * write bursts. If we're missing latency targets, consider the device
 * fully utilized.
 */
 if (ioc->busy_level > 0)
  usage_us_sum = max_t(u64, usage_us_sum, ioc->period_us);

 ioc->dfgv_usage_us_sum += usage_us_sum;
 if (time_before64(now->now, ioc->dfgv_period_at + DFGV_PERIOD))
  return;

 /*
 * At least DFGV_PERIOD has passed since the last period. Calculate the
 * average usage and reset the period counters.
 */
 dur = now->now - ioc->dfgv_period_at;
 usage_pct = div64_u64(100 * ioc->dfgv_usage_us_sum, dur);

 ioc->dfgv_period_at = now->now;
 ioc->dfgv_usage_us_sum = 0;

 /* if was too busy, reset everything */
 if (usage_pct > DFGV_USAGE_PCT) {
  ioc->dfgv_period_rem = 0;
  return;
 }

 /*
 * Usage is lower than threshold. Let's forgive some debts. Debt
 * forgiveness runs off of the usual ioc timer but its period usually
 * doesn't match ioc's. Compensate the difference by performing the
 * reduction as many times as would fit in the duration since the last
 * run and carrying over the left-over duration in @ioc->dfgv_period_rem
 * - if ioc period is 75% of DFGV_PERIOD, one out of three consecutive
 * reductions is doubled.
 */
 nr_cycles = dur + ioc->dfgv_period_rem;
 ioc->dfgv_period_rem = do_div(nr_cycles, DFGV_PERIOD);

 list_for_each_entry(iocg, &ioc->active_iocgs, active_list) {
  u64 __maybe_unused old_debt, __maybe_unused old_delay;

  if (!iocg->abs_vdebt && !iocg->delay)
   continue;

  spin_lock(&iocg->waitq.lock);

  old_debt = iocg->abs_vdebt;
  old_delay = iocg->delay;

  nr_cycles_shift = min_t(u64, nr_cycles, BITS_PER_LONG - 1);
  if (iocg->abs_vdebt)
   iocg->abs_vdebt = iocg->abs_vdebt >> nr_cycles_shift ?: 1;

  if (iocg->delay)
   iocg->delay = iocg->delay >> nr_cycles_shift ?: 1;

  iocg_kick_waitq(iocg, true, now);

  TRACE_IOCG_PATH(iocg_forgive_debt, iocg, now, usage_pct,
    old_debt, iocg->abs_vdebt,
    old_delay, iocg->delay);

  spin_unlock(&iocg->waitq.lock);
 }
}

/*
 * Check the active iocgs' state to avoid oversleeping and deactive
 * idle iocgs.
 *
 * Since waiters determine the sleep durations based on the vrate
 * they saw at the time of sleep, if vrate has increased, some
 * waiters could be sleeping for too long. Wake up tardy waiters
 * which should have woken up in the last period and expire idle
--> --------------------

--> maximum size reached

--> --------------------