cregit-Linux how code gets into the kernel

Release 4.12 block/blk-throttle.c

Directory: block
 * Interface for controlling IO bandwidth on a request queue
 * Copyright (C) 2010 Vivek Goyal <>

#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_IDLE_TIME (5L * 1000 * 1000) 
/* 5 s */

#define MIN_THROTL_BPS (320 * 1024)

#define MIN_THROTL_IOPS (10)



/* 4ms */

 * 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 */

#define SKIP_LATENCY (((u64)1) << BLK_STAT_RES_SHIFT)

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 {

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 */


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[LATENCY_BUCKET_SIZE];
struct avg_latency_bucket avg_buckets[LATENCY_BUCKET_SIZE];
struct latency_bucket __percpu *latency_buckets;
unsigned long last_calculate_time;
unsigned long filtered_latency;

bool track_bio_latency;

static void throtl_pending_timer_fn(unsigned long arg);

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


Tejun Heo29100.00%1100.00%

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


Tejun Heo26100.00%3100.00%

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


Tejun Heo23100.00%3100.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; }


Tejun Heo3494.44%150.00%
Vivek Goyal25.56%150.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); }


Tejun Heo44100.00%1100.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; }


Shaohua Li69100.00%1100.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; }


Shaohua Li196100.00%4100.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; }


Shaohua Li204100.00%4100.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)) { \ char __pbuf[128]; \ \ blkg_path(tg_to_blkg(__tg), __pbuf, sizeof(__pbuf)); \ blk_add_trace_msg(__td->queue, "throtl %s " fmt, __pbuf, ##args); \ } else { \ blk_add_trace_msg(__td->queue, "throtl " fmt, ##args); \ } \ } while (0)
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; }


Tejun Heo38100.00%1100.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)); } }


Tejun Heo63100.00%1100.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; }


Tejun Heo62100.00%1100.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; }


Tejun Heo123100.00%1100.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; setup_timer(&sq->pending_timer, throtl_pending_timer_fn, (unsigned long)sq); }


Tejun Heo55100.00%4100.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; }


Tejun Heo14061.14%545.45%
Shaohua Li8938.86%654.55%

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


Tejun Heo8894.62%1392.86%
Vivek Goyal55.38%17.14%

/* * 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)); }


Tejun Heo7070.71%133.33%
Shaohua Li2929.29%266.67%

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


Tejun Heo1762.96%266.67%
Shaohua Li1037.04%133.33%

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


Shaohua Li8781.31%120.00%
Tejun Heo2018.69%480.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); }


Shaohua Li8181.82%266.67%
Vivek Goyal1818.18%133.33%

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


Shaohua Li36100.00%1100.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; }


Shaohua Li5998.33%150.00%
Vivek Goyal11.67%150.00%

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


Vivek Goyal28100.00%1100.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; }


Vivek Goyal3577.78%133.33%
Tejun Heo1022.22%266.67%

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


Vivek Goyal3286.49%133.33%
Tejun Heo513.51%266.67%

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


Vivek Goyal13186.75%125.00%
Tejun Heo2013.25%375.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++; }


Vivek Goyal1858.06%120.00%
Tejun Heo1341.94%480.00%

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


Vivek Goyal1970.37%133.33%
Tejun Heo829.63%266.67%

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


Vivek Goyal2062.50%125.00%
Tejun Heo1237.50%375.00%

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


Vivek Goyal1875.00%133.33%
Tejun Heo625.00%266.67%

/* Call with queue lock held */
static void throtl_schedule_pending_timer(struct throtl_service_queue *sq, unsigned long expires) { unsigned long max_expire = jiffies + 8 * sq_to_td(sq)->throtl_slice; /* * Since we are adjusting the throttle limit dynamically, the sleep * time calculated according to previous limit might be invalid. It's * possible the cgroup sleep time is very long and no other cgroups * have IO running so notify the limit changes. Make sure the cgroup * doesn't sleep too long to avoid the missed notification. */ if (time_after(expires, max_expire)) expires = max_expire; mod_timer(&sq->pending_timer,