Release 4.18 block/blk-throttle.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Interface for controlling IO bandwidth on a request queue
 *
 * Copyright (C) 2010 Vivek Goyal <vgoyal@redhat.com>
 */

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/blkdev.h>
#include <linux/bio.h>
#include <linux/blktrace_api.h>
#include <linux/blk-cgroup.h>
#include "blk.h"

/* Max dispatch from a group in 1 round */

static int throtl_grp_quantum = 8;

/* Total max dispatch from all groups in one round */

static int throtl_quantum = 32;

/* Throttling is performed over a slice and after that slice is renewed */

#define DFL_THROTL_SLICE_HD (HZ / 10)

#define DFL_THROTL_SLICE_SSD (HZ / 50)

#define MAX_THROTL_SLICE (HZ)

#define MAX_IDLE_TIME (5L * 1000 * 1000) 
/* 5 s */

#define MIN_THROTL_BPS (320 * 1024)

#define MIN_THROTL_IOPS (10)

#define DFL_LATENCY_TARGET (-1L)

#define DFL_IDLE_THRESHOLD (0)

#define DFL_HD_BASELINE_LATENCY (4000L) 
/* 4ms */

#define LATENCY_FILTERED_SSD (0)
/*
 * For HD, very small latency comes from sequential IO. Such IO is helpless to
 * help determine if its IO is impacted by others, hence we ignore the IO
 */

#define LATENCY_FILTERED_HD (1000L) 
/* 1ms */


static struct blkcg_policy blkcg_policy_throtl;

/* A workqueue to queue throttle related work */

static struct workqueue_struct *kthrotld_workqueue;

/*
 * To implement hierarchical throttling, throtl_grps form a tree and bios
 * are dispatched upwards level by level until they reach the top and get
 * issued.  When dispatching bios from the children and local group at each
 * level, if the bios are dispatched into a single bio_list, there's a risk
 * of a local or child group which can queue many bios at once filling up
 * the list starving others.
 *
 * To avoid such starvation, dispatched bios are queued separately
 * according to where they came from.  When they are again dispatched to
 * the parent, they're popped in round-robin order so that no single source
 * hogs the dispatch window.
 *
 * throtl_qnode is used to keep the queued bios separated by their sources.
 * Bios are queued to throtl_qnode which in turn is queued to
 * throtl_service_queue and then dispatched in round-robin order.
 *
 * It's also used to track the reference counts on blkg's.  A qnode always
 * belongs to a throtl_grp and gets queued on itself or the parent, so
 * incrementing the reference of the associated throtl_grp when a qnode is
 * queued and decrementing when dequeued is enough to keep the whole blkg
 * tree pinned while bios are in flight.
 */

struct throtl_qnode {
	
struct list_head	node;		/* service_queue->queued[] */
	
struct bio_list		bios;		/* queued bios */
	
struct throtl_grp	*tg;		/* tg this qnode belongs to */
};


struct throtl_service_queue {
	
struct throtl_service_queue *parent_sq;	/* the parent service_queue */

	/*
         * Bios queued directly to this service_queue or dispatched from
         * children throtl_grp's.
         */
	
struct list_head	queued[2];	/* throtl_qnode [READ/WRITE] */
	
unsigned int		nr_queued[2];	/* number of queued bios */

	/*
         * RB tree of active children throtl_grp's, which are sorted by
         * their ->disptime.
         */
	
struct rb_root		pending_tree;	/* RB tree of active tgs */
	
struct rb_node		*first_pending;	/* first node in the tree */
	
unsigned int		nr_pending;	/* # queued in the tree */
	
unsigned long		first_pending_disptime;	/* disptime of the first tg */
	
struct timer_list	pending_timer;	/* fires on first_pending_disptime */
};


enum tg_state_flags {
	
THROTL_TG_PENDING	= 1 << 0,	/* on parent's pending tree */
	
THROTL_TG_WAS_EMPTY	= 1 << 1,	/* bio_lists[] became non-empty */
};


#define rb_entry_tg(node)	rb_entry((node), struct throtl_grp, rb_node)


enum {
	
LIMIT_LOW,
	
LIMIT_MAX,
	
LIMIT_CNT,
};


struct throtl_grp {
	/* must be the first member */
	
struct blkg_policy_data pd;

	/* active throtl group service_queue member */
	
struct rb_node rb_node;

	/* throtl_data this group belongs to */
	
struct throtl_data *td;

	/* this group's service queue */
	
struct throtl_service_queue service_queue;

	/*
         * qnode_on_self is used when bios are directly queued to this
         * throtl_grp so that local bios compete fairly with bios
         * dispatched from children.  qnode_on_parent is used when bios are
         * dispatched from this throtl_grp into its parent and will compete
         * with the sibling qnode_on_parents and the parent's
         * qnode_on_self.
         */
	
struct throtl_qnode qnode_on_self[2];
	
struct throtl_qnode qnode_on_parent[2];

	/*
         * Dispatch time in jiffies. This is the estimated time when group
         * will unthrottle and is ready to dispatch more bio. It is used as
         * key to sort active groups in service tree.
         */
	
unsigned long disptime;

	
unsigned int flags;

	/* are there any throtl rules between this group and td? */
	
bool has_rules[2];

	/* internally used bytes per second rate limits */
	
uint64_t bps[2][LIMIT_CNT];
	/* user configured bps limits */
	
uint64_t bps_conf[2][LIMIT_CNT];

	/* internally used IOPS limits */
	
unsigned int iops[2][LIMIT_CNT];
	/* user configured IOPS limits */
	
unsigned int iops_conf[2][LIMIT_CNT];

	/* Number of bytes disptached in current slice */
	
uint64_t bytes_disp[2];
	/* Number of bio's dispatched in current slice */
	
unsigned int io_disp[2];

	
unsigned long last_low_overflow_time[2];

	
uint64_t last_bytes_disp[2];
	
unsigned int last_io_disp[2];

	
unsigned long last_check_time;

	
unsigned long latency_target; /* us */
	
unsigned long latency_target_conf; /* us */
	/* When did we start a new slice */
	
unsigned long slice_start[2];
	
unsigned long slice_end[2];

	
unsigned long last_finish_time; /* ns / 1024 */
	
unsigned long checked_last_finish_time; /* ns / 1024 */
	
unsigned long avg_idletime; /* ns / 1024 */
	
unsigned long idletime_threshold; /* us */
	
unsigned long idletime_threshold_conf; /* us */

	
unsigned int bio_cnt; /* total bios */
	
unsigned int bad_bio_cnt; /* bios exceeding latency threshold */
	
unsigned long bio_cnt_reset_time;
};

/* We measure latency for request size from <= 4k to >= 1M */

#define LATENCY_BUCKET_SIZE 9


struct latency_bucket {
	
unsigned long total_latency; /* ns / 1024 */
	
int samples;
};


struct avg_latency_bucket {
	
unsigned long latency; /* ns / 1024 */
	
bool valid;
};


struct throtl_data
{
	/* service tree for active throtl groups */
	
struct throtl_service_queue service_queue;

	
struct request_queue *queue;

	/* Total Number of queued bios on READ and WRITE lists */
	
unsigned int nr_queued[2];

	
unsigned int throtl_slice;

	/* Work for dispatching throttled bios */
	
struct work_struct dispatch_work;
	
unsigned int limit_index;
	
bool limit_valid[LIMIT_CNT];

	
unsigned long low_upgrade_time;
	
unsigned long low_downgrade_time;

	
unsigned int scale;

	
struct latency_bucket tmp_buckets[2][LATENCY_BUCKET_SIZE];
	
struct avg_latency_bucket avg_buckets[2][LATENCY_BUCKET_SIZE];
	
struct latency_bucket __percpu *latency_buckets[2];
	
unsigned long last_calculate_time;
	
unsigned long filtered_latency;

	
bool track_bio_latency;
};

static void throtl_pending_timer_fn(struct timer_list *t);



static inline struct throtl_grp *pd_to_tg(struct blkg_policy_data *pd)
{
	return pd ? container_of(pd, struct throtl_grp, pd) : NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
29
100.00%
1
100.00%
Total
29
100.00%
1
100.00%



static inline struct throtl_grp *blkg_to_tg(struct blkcg_gq *blkg)
{
	return pd_to_tg(blkg_to_pd(blkg, &blkcg_policy_throtl));
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
26
100.00%
3
100.00%
Total
26
100.00%
3
100.00%



static inline struct blkcg_gq *tg_to_blkg(struct throtl_grp *tg)
{
	return pd_to_blkg(&tg->pd);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
23
100.00%
3
100.00%
Total
23
100.00%
3
100.00%

/**
 * sq_to_tg - return the throl_grp the specified service queue belongs to
 * @sq: the throtl_service_queue of interest
 *
 * Return the throtl_grp @sq belongs to.  If @sq is the top-level one
 * embedded in throtl_data, %NULL is returned.
 */


static struct throtl_grp *sq_to_tg(struct throtl_service_queue *sq)
{
	if (sq && sq->parent_sq)
		return container_of(sq, struct throtl_grp, service_queue);
	else
		return NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
34
94.44%
1
50.00%
Vivek Goyal
2
5.56%
1
50.00%
Total
36
100.00%
2
100.00%

/**
 * sq_to_td - return throtl_data the specified service queue belongs to
 * @sq: the throtl_service_queue of interest
 *
 * A service_queue can be embedded in either a throtl_grp or throtl_data.
 * Determine the associated throtl_data accordingly and return it.
 */


static struct throtl_data *sq_to_td(struct throtl_service_queue *sq)
{
	struct throtl_grp *tg = sq_to_tg(sq);

	if (tg)
		return tg->td;
	else
		return container_of(sq, struct throtl_data, service_queue);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
44
100.00%
1
100.00%
Total
44
100.00%
1
100.00%

/*
 * cgroup's limit in LIMIT_MAX is scaled if low limit is set. This scale is to
 * make the IO dispatch more smooth.
 * Scale up: linearly scale up according to lapsed time since upgrade. For
 *           every throtl_slice, the limit scales up 1/2 .low limit till the
 *           limit hits .max limit
 * Scale down: exponentially scale down if a cgroup doesn't hit its .low limit
 */


static uint64_t throtl_adjusted_limit(uint64_t low, struct throtl_data *td)
{
	/* arbitrary value to avoid too big scale */
	if (td->scale < 4096 && time_after_eq(jiffies,
	    td->low_upgrade_time + td->scale * td->throtl_slice))
		td->scale = (jiffies - td->low_upgrade_time) / td->throtl_slice;

	return low + (low >> 1) * td->scale;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
69
100.00%
1
100.00%
Total
69
100.00%
1
100.00%



static uint64_t tg_bps_limit(struct throtl_grp *tg, int rw)
{
	struct blkcg_gq *blkg = tg_to_blkg(tg);
	struct throtl_data *td;
	uint64_t ret;

	if (cgroup_subsys_on_dfl(io_cgrp_subsys) && !blkg->parent)
		return U64_MAX;

	td = tg->td;
	ret = tg->bps[rw][td->limit_index];
	if (ret == 0 && td->limit_index == LIMIT_LOW) {
		/* intermediate node or iops isn't 0 */
		if (!list_empty(&blkg->blkcg->css.children) ||
		    tg->iops[rw][td->limit_index])
			return U64_MAX;
		else
			return MIN_THROTL_BPS;
	}

	if (td->limit_index == LIMIT_MAX && tg->bps[rw][LIMIT_LOW] &&
	    tg->bps[rw][LIMIT_LOW] != tg->bps[rw][LIMIT_MAX]) {
		uint64_t adjusted;

		adjusted = throtl_adjusted_limit(tg->bps[rw][LIMIT_LOW], td);
		ret = min(tg->bps[rw][LIMIT_MAX], adjusted);
	}
	return ret;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
196
100.00%
4
100.00%
Total
196
100.00%
4
100.00%



static unsigned int tg_iops_limit(struct throtl_grp *tg, int rw)
{
	struct blkcg_gq *blkg = tg_to_blkg(tg);
	struct throtl_data *td;
	unsigned int ret;

	if (cgroup_subsys_on_dfl(io_cgrp_subsys) && !blkg->parent)
		return UINT_MAX;

	td = tg->td;
	ret = tg->iops[rw][td->limit_index];
	if (ret == 0 && tg->td->limit_index == LIMIT_LOW) {
		/* intermediate node or bps isn't 0 */
		if (!list_empty(&blkg->blkcg->css.children) ||
		    tg->bps[rw][td->limit_index])
			return UINT_MAX;
		else
			return MIN_THROTL_IOPS;
	}

	if (td->limit_index == LIMIT_MAX && tg->iops[rw][LIMIT_LOW] &&
	    tg->iops[rw][LIMIT_LOW] != tg->iops[rw][LIMIT_MAX]) {
		uint64_t adjusted;

		adjusted = throtl_adjusted_limit(tg->iops[rw][LIMIT_LOW], td);
		if (adjusted > UINT_MAX)
			adjusted = UINT_MAX;
		ret = min_t(unsigned int, tg->iops[rw][LIMIT_MAX], adjusted);
	}
	return ret;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
204
100.00%
4
100.00%
Total
204
100.00%
4
100.00%


#define request_bucket_index(sectors) \
	clamp_t(int, order_base_2(sectors) - 3, 0, LATENCY_BUCKET_SIZE - 1)

/**
 * throtl_log - log debug message via blktrace
 * @sq: the service_queue being reported
 * @fmt: printf format string
 * @args: printf args
 *
 * The messages are prefixed with "throtl BLKG_NAME" if @sq belongs to a
 * throtl_grp; otherwise, just "throtl".
 */

#define throtl_log(sq, fmt, args...)	do {                            \
        struct throtl_grp *__tg = sq_to_tg((sq));                       \
        struct throtl_data *__td = sq_to_td((sq));                      \
                                                                        \
        (void)__td;                                                     \
        if (likely(!blk_trace_note_message_enabled(__td->queue)))       \
                break;                                                  \
        if ((__tg)) {                                                   \
                blk_add_cgroup_trace_msg(__td->queue,                   \
                        tg_to_blkg(__tg)->blkcg, "throtl " fmt, ##args);\
        } else {                                                        \
                blk_add_trace_msg(__td->queue, "throtl " fmt, ##args);  \
        }                                                               \
} while (0)



static inline unsigned int throtl_bio_data_size(struct bio *bio)
{
	/* assume it's one sector */
	if (unlikely(bio_op(bio) == REQ_OP_DISCARD))
		return 512;
	return bio->bi_iter.bi_size;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
36
100.00%
1
100.00%
Total
36
100.00%
1
100.00%



static void throtl_qnode_init(struct throtl_qnode *qn, struct throtl_grp *tg)
{
	INIT_LIST_HEAD(&qn->node);
	bio_list_init(&qn->bios);
	qn->tg = tg;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
38
100.00%
1
100.00%
Total
38
100.00%
1
100.00%

/**
 * throtl_qnode_add_bio - add a bio to a throtl_qnode and activate it
 * @bio: bio being added
 * @qn: qnode to add bio to
 * @queued: the service_queue->queued[] list @qn belongs to
 *
 * Add @bio to @qn and put @qn on @queued if it's not already on.
 * @qn->tg's reference count is bumped when @qn is activated.  See the
 * comment on top of throtl_qnode definition for details.
 */


static void throtl_qnode_add_bio(struct bio *bio, struct throtl_qnode *qn,
				 struct list_head *queued)
{
	bio_list_add(&qn->bios, bio);
	if (list_empty(&qn->node)) {
		list_add_tail(&qn->node, queued);
		blkg_get(tg_to_blkg(qn->tg));
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
63
100.00%
1
100.00%
Total
63
100.00%
1
100.00%

/**
 * throtl_peek_queued - peek the first bio on a qnode list
 * @queued: the qnode list to peek
 */


static struct bio *throtl_peek_queued(struct list_head *queued)
{
	struct throtl_qnode *qn = list_first_entry(queued, struct throtl_qnode, node);
	struct bio *bio;

	if (list_empty(queued))
		return NULL;

	bio = bio_list_peek(&qn->bios);
	WARN_ON_ONCE(!bio);
	return bio;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
62
100.00%
1
100.00%
Total
62
100.00%
1
100.00%

/**
 * throtl_pop_queued - pop the first bio form a qnode list
 * @queued: the qnode list to pop a bio from
 * @tg_to_put: optional out argument for throtl_grp to put
 *
 * Pop the first bio from the qnode list @queued.  After popping, the first
 * qnode is removed from @queued if empty or moved to the end of @queued so
 * that the popping order is round-robin.
 *
 * When the first qnode is removed, its associated throtl_grp should be put
 * too.  If @tg_to_put is NULL, this function automatically puts it;
 * otherwise, *@tg_to_put is set to the throtl_grp to put and the caller is
 * responsible for putting it.
 */


static struct bio *throtl_pop_queued(struct list_head *queued,
				     struct throtl_grp **tg_to_put)
{
	struct throtl_qnode *qn = list_first_entry(queued, struct throtl_qnode, node);
	struct bio *bio;

	if (list_empty(queued))
		return NULL;

	bio = bio_list_pop(&qn->bios);
	WARN_ON_ONCE(!bio);

	if (bio_list_empty(&qn->bios)) {
		list_del_init(&qn->node);
		if (tg_to_put)
			*tg_to_put = qn->tg;
		else
			blkg_put(tg_to_blkg(qn->tg));
	} else {
		list_move_tail(&qn->node, queued);
	}

	return bio;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
123
100.00%
1
100.00%
Total
123
100.00%
1
100.00%

/* init a service_queue, assumes the caller zeroed it */


static void throtl_service_queue_init(struct throtl_service_queue *sq)
{
	INIT_LIST_HEAD(&sq->queued[0]);
	INIT_LIST_HEAD(&sq->queued[1]);
	sq->pending_tree = RB_ROOT;
	timer_setup(&sq->pending_timer, throtl_pending_timer_fn, 0);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
49
96.08%
4
80.00%
Kees Cook
2
3.92%
1
20.00%
Total
51
100.00%
5
100.00%



static struct blkg_policy_data *throtl_pd_alloc(gfp_t gfp, int node)
{
	struct throtl_grp *tg;
	int rw;

	tg = kzalloc_node(sizeof(*tg), gfp, node);
	if (!tg)
		return NULL;

	throtl_service_queue_init(&tg->service_queue);

	for (rw = READ; rw <= WRITE; rw++) {
		throtl_qnode_init(&tg->qnode_on_self[rw], tg);
		throtl_qnode_init(&tg->qnode_on_parent[rw], tg);
	}

	RB_CLEAR_NODE(&tg->rb_node);
	tg->bps[READ][LIMIT_MAX] = U64_MAX;
	tg->bps[WRITE][LIMIT_MAX] = U64_MAX;
	tg->iops[READ][LIMIT_MAX] = UINT_MAX;
	tg->iops[WRITE][LIMIT_MAX] = UINT_MAX;
	tg->bps_conf[READ][LIMIT_MAX] = U64_MAX;
	tg->bps_conf[WRITE][LIMIT_MAX] = U64_MAX;
	tg->iops_conf[READ][LIMIT_MAX] = UINT_MAX;
	tg->iops_conf[WRITE][LIMIT_MAX] = UINT_MAX;
	/* LIMIT_LOW will have default value 0 */

	tg->latency_target = DFL_LATENCY_TARGET;
	tg->latency_target_conf = DFL_LATENCY_TARGET;
	tg->idletime_threshold = DFL_IDLE_THRESHOLD;
	tg->idletime_threshold_conf = DFL_IDLE_THRESHOLD;

	return &tg->pd;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
140
61.14%
5
45.45%
Shaohua Li
89
38.86%
6
54.55%
Total
229
100.00%
11
100.00%



static void throtl_pd_init(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);
	struct blkcg_gq *blkg = tg_to_blkg(tg);
	struct throtl_data *td = blkg->q->td;
	struct throtl_service_queue *sq = &tg->service_queue;

	/*
         * If on the default hierarchy, we switch to properly hierarchical
         * behavior where limits on a given throtl_grp are applied to the
         * whole subtree rather than just the group itself.  e.g. If 16M
         * read_bps limit is set on the root group, the whole system can't
         * exceed 16M for the device.
         *
         * If not on the default hierarchy, the broken flat hierarchy
         * behavior is retained where all throtl_grps are treated as if
         * they're all separate root groups right below throtl_data.
         * Limits of a group don't interact with limits of other groups
         * regardless of the position of the group in the hierarchy.
         */
	sq->parent_sq = &td->service_queue;
	if (cgroup_subsys_on_dfl(io_cgrp_subsys) && blkg->parent)
		sq->parent_sq = &blkg_to_tg(blkg->parent)->service_queue;
	tg->td = td;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
88
94.62%
13
92.86%
Vivek Goyal
5
5.38%
1
7.14%
Total
93
100.00%
14
100.00%

/*
 * Set has_rules[] if @tg or any of its parents have limits configured.
 * This doesn't require walking up to the top of the hierarchy as the
 * parent's has_rules[] is guaranteed to be correct.
 */


static void tg_update_has_rules(struct throtl_grp *tg)
{
	struct throtl_grp *parent_tg = sq_to_tg(tg->service_queue.parent_sq);
	struct throtl_data *td = tg->td;
	int rw;

	for (rw = READ; rw <= WRITE; rw++)
		tg->has_rules[rw] = (parent_tg && parent_tg->has_rules[rw]) ||
			(td->limit_valid[td->limit_index] &&
			 (tg_bps_limit(tg, rw) != U64_MAX ||
			  tg_iops_limit(tg, rw) != UINT_MAX));
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
70
70.71%
1
33.33%
Shaohua Li
29
29.29%
2
66.67%
Total
99
100.00%
3
100.00%



static void throtl_pd_online(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);
	/*
         * We don't want new groups to escape the limits of its ancestors.
         * Update has_rules[] after a new group is brought online.
         */
	tg_update_has_rules(tg);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Tejun Heo
17
62.96%
2
66.67%
Shaohua Li
10
37.04%
1
33.33%
Total
27
100.00%
3
100.00%



static void blk_throtl_update_limit_valid(struct throtl_data *td)
{
	struct cgroup_subsys_state *pos_css;
	struct blkcg_gq *blkg;
	bool low_valid = false;

	rcu_read_lock();
	blkg_for_each_descendant_post(blkg, pos_css, td->queue->root_blkg) {
		struct throtl_grp *tg = blkg_to_tg(blkg);

		if (tg->bps[READ][LIMIT_LOW] || tg->bps[WRITE][LIMIT_LOW] ||
		    tg->iops[READ][LIMIT_LOW] || tg->iops[WRITE][LIMIT_LOW])
			low_valid = true;
	}
	rcu_read_unlock();

	td->limit_valid[LIMIT_LOW] = low_valid;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
87
81.31%
1
20.00%
Tejun Heo
20
18.69%
4
80.00%
Total
107
100.00%
5
100.00%

static void throtl_upgrade_state(struct throtl_data *td);


static void throtl_pd_offline(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);

	tg->bps[READ][LIMIT_LOW] = 0;
	tg->bps[WRITE][LIMIT_LOW] = 0;
	tg->iops[READ][LIMIT_LOW] = 0;
	tg->iops[WRITE][LIMIT_LOW] = 0;

	blk_throtl_update_limit_valid(tg->td);

	if (!tg->td->limit_valid[tg->td->limit_index])
		throtl_upgrade_state(tg->td);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
81
81.82%
2
66.67%
Vivek Goyal
18
18.18%
1
33.33%
Total
99
100.00%
3
100.00%



static void throtl_pd_free(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);

	del_timer_sync(&tg->service_queue.pending_timer);
	kfree(tg);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
36
100.00%
1
100.00%
Total
36
100.00%
1
100.00%


static struct throtl_grp *

throtl_rb_first(struct throtl_service_queue *parent_sq)
{
	/* Service tree is empty */
	if (!parent_sq->nr_pending)
		return NULL;

	if (!parent_sq->first_pending)
		parent_sq->first_pending = rb_first(&parent_sq->pending_tree);

	if (parent_sq->first_pending)
		return rb_entry_tg(parent_sq->first_pending);

	return NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Shaohua Li
59
98.33%
1
50.00%
Vivek Goyal
1
1.67%
1
50.00%
Total
60
100.00%
2
100.00%



static void rb_erase_init(struct rb_node *n, struct rb_root *root)
{
	rb_erase(n, root);
	RB_CLEAR_NODE(n);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
28
100.00%
1
100.00%
Total
28
100.00%
1
100.00%



static void throtl_rb_erase(struct rb_node *n,
			    struct throtl_service_queue *parent_sq)
{
	if (parent_sq->first_pending == n)
		parent_sq->first_pending = NULL;
	rb_erase_init(n, &parent_sq->pending_tree);
	--parent_sq->nr_pending;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
35
77.78%
1
33.33%
Tejun Heo
10
22.22%
2
66.67%
Total
45
100.00%
3
100.00%



static void update_min_dispatch_time(struct throtl_service_queue *parent_sq)
{
	struct throtl_grp *tg;

	tg = throtl_rb_first(parent_sq);
	if (!tg)
		return;

	parent_sq->first_pending_disptime = tg->disptime;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
32
86.49%
1
33.33%
Tejun Heo
5
13.51%
2
66.67%
Total
37
100.00%
3
100.00%



static void tg_service_queue_add(struct throtl_grp *tg)
{
	struct throtl_service_queue *parent_sq = tg->service_queue.parent_sq;
	struct rb_node **node = &parent_sq->pending_tree.rb_node;
	struct rb_node *parent = NULL;
	struct throtl_grp *__tg;
	unsigned long key = tg->disptime;
	int left = 1;

	while (*node != NULL) {
		parent = *node;
		__tg = rb_entry_tg(parent);

		if (time_before(key, __tg->disptime))
			node = &parent->rb_left;
		else {
			node = &parent->rb_right;
			left = 0;
		}
	}

	if (left)
		parent_sq->first_pending = &tg->rb_node;

	rb_link_node(&tg->rb_node, parent, node);
	rb_insert_color(&tg->rb_node, &parent_sq->pending_tree);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
131
86.75%
1
25.00%
Tejun Heo
20
13.25%
3
75.00%
Total
151
100.00%
4
100.00%



static void __throtl_enqueue_tg(struct throtl_grp *tg)
{
	tg_service_queue_add(tg);
	tg->flags |= THROTL_TG_PENDING;
	tg->service_queue.parent_sq->nr_pending++;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
18
58.06%
1
20.00%
Tejun Heo
13
41.94%
4
80.00%
Total
31
100.00%
5
100.00%



static void throtl_enqueue_tg(struct throtl_grp *tg)
{
	if (!(tg->flags & THROTL_TG_PENDING))
		__throtl_enqueue_tg(tg);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
19
70.37%
1
33.33%
Tejun Heo
8
29.63%
2
66.67%
Total
27
100.00%
3
100.00%



static void __throtl_dequeue_tg(struct throtl_grp *tg)
{
	throtl_rb_erase(&tg->rb_node, tg->service_queue.parent_sq);
	tg->flags &= ~THROTL_TG_PENDING;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
20
62.50%
1
25.00%
Tejun Heo
12
37.50%
3
75.00%
Total
32
100.00%
4
100.00%



static void throtl_dequeue_tg(struct throtl_grp *tg)
{
	if (tg->flags & THROTL_TG_PENDING)
		__throtl_dequeue_tg(tg);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vivek Goyal
18
75.00%
1
33.33%
Tejun Heo
6
25.00%
2
66.67%
Total
24
100.00%
3
100.00%

/* Call with queue lock held */


static void throtl_schedule_pending_timer(struct throtl_service_queue *sq