#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

#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,

/*

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 {

/*

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,

/*

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,

/*

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,

};

enum {

QOS_ENABLE,

QOS_CTRL,

NR_QOS_CTRL_PARAMS,

};

enum {

QOS_RPPM,

QOS_RLAT,

QOS_WPPM,

QOS_WLAT,

QOS_MIN,

QOS_MAX,

NR_QOS_PARAMS,

};

enum {

COST_CTRL,

COST_MODEL,

NR_COST_CTRL_PARAMS,

};

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;

};

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;

};

struct ioc_gq {

struct blkg_policy_data pd;

struct ioc *ioc;

/*

u32 cfg_weight;

u32 weight;

u32 active;

u32 inuse;

u32 last_inuse;

s64 saved_margin;

sector_t cursor; /* to detect randio */

/*

atomic64_t vtime;

atomic64_t done_vtime;

u64 abs_vdebt;

/* current delay in effect and when it started */

u64 delay;

u64 delay_at;

/*

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[];

};

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,

},

};

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;

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 "<unknown>";

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);

}

static u64 abs_cost_to_cost(u64 abs_cost, u32 hw_inuse)

{

return DIV64_U64_ROUND_UP(abs_cost * WEIGHT_ONE, hw_inuse);

}

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);

}

#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;

}

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];

}

/*

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);

}

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_rot(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;

}

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]);

}

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);

}

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;

/*

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 < 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 {