blk-throttle.c 68.7 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2 3 4 5 6 7 8 9 10 11 12
/*
 * 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>
13
#include <linux/blk-cgroup.h>
14
#include "blk.h"
15 16 17 18 19 20 21

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

22 23 24
/* 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)
25
#define MAX_THROTL_SLICE (HZ)
26
#define MAX_IDLE_TIME (5L * 1000 * 1000) /* 5 s */
27 28
#define MIN_THROTL_BPS (320 * 1024)
#define MIN_THROTL_IOPS (10)
29 30
#define DFL_LATENCY_TARGET (-1L)
#define DFL_IDLE_THRESHOLD (0)
31 32 33 34 35 36 37
#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 */
38

Tejun Heo's avatar
Tejun Heo committed
39
static struct blkcg_policy blkcg_policy_throtl;
40

41 42 43
/* A workqueue to queue throttle related work */
static struct workqueue_struct *kthrotld_workqueue;

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
/*
 * 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 */
};

73
struct throtl_service_queue {
74 75
	struct throtl_service_queue *parent_sq;	/* the parent service_queue */

76 77 78 79
	/*
	 * Bios queued directly to this service_queue or dispatched from
	 * children throtl_grp's.
	 */
80
	struct list_head	queued[2];	/* throtl_qnode [READ/WRITE] */
81 82 83 84 85 86
	unsigned int		nr_queued[2];	/* number of queued bios */

	/*
	 * RB tree of active children throtl_grp's, which are sorted by
	 * their ->disptime.
	 */
87 88 89 90
	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 */
91
	struct timer_list	pending_timer;	/* fires on first_pending_disptime */
92 93
};

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

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

101
enum {
102
	LIMIT_LOW,
103 104 105 106
	LIMIT_MAX,
	LIMIT_CNT,
};

107
struct throtl_grp {
108 109 110
	/* must be the first member */
	struct blkg_policy_data pd;

111
	/* active throtl group service_queue member */
112 113
	struct rb_node rb_node;

114 115 116
	/* throtl_data this group belongs to */
	struct throtl_data *td;

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

120 121 122 123 124 125 126 127 128 129 130
	/*
	 * 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];

131 132 133 134 135 136 137 138 139
	/*
	 * 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;

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

143
	/* internally used bytes per second rate limits */
144
	uint64_t bps[2][LIMIT_CNT];
145 146
	/* user configured bps limits */
	uint64_t bps_conf[2][LIMIT_CNT];
147

148
	/* internally used IOPS limits */
149
	unsigned int iops[2][LIMIT_CNT];
150 151
	/* user configured IOPS limits */
	unsigned int iops_conf[2][LIMIT_CNT];
152

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

158 159 160 161 162 163 164
	unsigned long last_low_overflow_time[2];

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

	unsigned long last_check_time;

165
	unsigned long latency_target; /* us */
166
	unsigned long latency_target_conf; /* us */
167 168 169
	/* When did we start a new slice */
	unsigned long slice_start[2];
	unsigned long slice_end[2];
170 171 172 173 174

	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 */
175
	unsigned long idletime_threshold_conf; /* us */
176 177 178 179

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

182 183 184 185 186 187 188 189 190 191 192 193 194
/* 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;
};

195 196 197
struct throtl_data
{
	/* service tree for active throtl groups */
198
	struct throtl_service_queue service_queue;
199 200 201 202 203 204

	struct request_queue *queue;

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

205 206
	unsigned int throtl_slice;

207
	/* Work for dispatching throttled bios */
208
	struct work_struct dispatch_work;
209 210
	unsigned int limit_index;
	bool limit_valid[LIMIT_CNT];
211 212 213

	unsigned long low_upgrade_time;
	unsigned long low_downgrade_time;
214 215

	unsigned int scale;
216

217 218 219
	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];
220
	unsigned long last_calculate_time;
221
	unsigned long filtered_latency;
222 223

	bool track_bio_latency;
224 225
};

226
static void throtl_pending_timer_fn(struct timer_list *t);
227

228 229 230 231 232
static inline struct throtl_grp *pd_to_tg(struct blkg_policy_data *pd)
{
	return pd ? container_of(pd, struct throtl_grp, pd) : NULL;
}

Tejun Heo's avatar
Tejun Heo committed
233
static inline struct throtl_grp *blkg_to_tg(struct blkcg_gq *blkg)
234
{
235
	return pd_to_tg(blkg_to_pd(blkg, &blkcg_policy_throtl));
236 237
}

Tejun Heo's avatar
Tejun Heo committed
238
static inline struct blkcg_gq *tg_to_blkg(struct throtl_grp *tg)
239
{
240
	return pd_to_blkg(&tg->pd);
241 242
}

243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
/**
 * 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;
}

/**
 * sq_to_td - return throtl_data the specified service queue belongs to
 * @sq: the throtl_service_queue of interest
 *
262
 * A service_queue can be embedded in either a throtl_grp or throtl_data.
263 264 265 266 267 268 269 270 271 272 273 274
 * 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);
}

275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
/*
 * 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;
}

293 294
static uint64_t tg_bps_limit(struct throtl_grp *tg, int rw)
{
295
	struct blkcg_gq *blkg = tg_to_blkg(tg);
296
	struct throtl_data *td;
297 298 299 300
	uint64_t ret;

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

	td = tg->td;
	ret = tg->bps[rw][td->limit_index];
304 305 306 307 308 309 310 311
	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;
	}
312 313 314 315 316 317 318 319

	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);
	}
320
	return ret;
321 322 323 324
}

static unsigned int tg_iops_limit(struct throtl_grp *tg, int rw)
{
325
	struct blkcg_gq *blkg = tg_to_blkg(tg);
326
	struct throtl_data *td;
327 328 329 330
	unsigned int ret;

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

332 333
	td = tg->td;
	ret = tg->iops[rw][td->limit_index];
334 335 336 337 338 339 340 341
	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;
	}
342 343 344 345 346 347 348 349 350 351

	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);
	}
352
	return ret;
353 354
}

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

358 359 360 361 362 363 364 365 366 367 368 369 370 371
/**
 * 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;							\
372 373
	if (likely(!blk_trace_note_message_enabled(__td->queue)))	\
		break;							\
374
	if ((__tg)) {							\
375 376
		blk_add_cgroup_trace_msg(__td->queue,			\
			tg_to_blkg(__tg)->blkcg, "throtl " fmt, ##args);\
377 378 379
	} else {							\
		blk_add_trace_msg(__td->queue, "throtl " fmt, ##args);	\
	}								\
380
} while (0)
381

382 383 384 385 386 387 388 389
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;
}

390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472
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;
}

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

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

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

473
/* init a service_queue, assumes the caller zeroed it */
474
static void throtl_service_queue_init(struct throtl_service_queue *sq)
475
{
476 477
	INIT_LIST_HEAD(&sq->queued[0]);
	INIT_LIST_HEAD(&sq->queued[1]);
478
	sq->pending_tree = RB_ROOT;
479
	timer_setup(&sq->pending_timer, throtl_pending_timer_fn, 0);
480 481
}

482 483
static struct blkg_policy_data *throtl_pd_alloc(gfp_t gfp, int node)
{
484
	struct throtl_grp *tg;
485
	int rw;
486 487 488

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

491 492 493 494 495 496 497 498
	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);
499 500 501 502
	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;
503 504 505 506 507
	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 */
508

509
	tg->latency_target = DFL_LATENCY_TARGET;
510
	tg->latency_target_conf = DFL_LATENCY_TARGET;
511 512
	tg->idletime_threshold = DFL_IDLE_THRESHOLD;
	tg->idletime_threshold_conf = DFL_IDLE_THRESHOLD;
513

514
	return &tg->pd;
515 516
}

517
static void throtl_pd_init(struct blkg_policy_data *pd)
518
{
519 520
	struct throtl_grp *tg = pd_to_tg(pd);
	struct blkcg_gq *blkg = tg_to_blkg(tg);
521
	struct throtl_data *td = blkg->q->td;
522
	struct throtl_service_queue *sq = &tg->service_queue;
523

524
	/*
525
	 * If on the default hierarchy, we switch to properly hierarchical
526 527 528 529 530
	 * 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.
	 *
531
	 * If not on the default hierarchy, the broken flat hierarchy
532 533 534 535 536
	 * 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.
	 */
537
	sq->parent_sq = &td->service_queue;
538
	if (cgroup_subsys_on_dfl(io_cgrp_subsys) && blkg->parent)
539
		sq->parent_sq = &blkg_to_tg(blkg->parent)->service_queue;
540
	tg->td = td;
541 542
}

543 544 545 546 547 548 549 550
/*
 * 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);
551
	struct throtl_data *td = tg->td;
552 553 554 555
	int rw;

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

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

571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
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;
}

590
static void throtl_upgrade_state(struct throtl_data *td);
591 592 593 594 595 596 597 598 599 600 601
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);

602 603
	if (!tg->td->limit_valid[tg->td->limit_index])
		throtl_upgrade_state(tg->td);
604 605
}

606 607
static void throtl_pd_free(struct blkg_policy_data *pd)
{
608 609
	struct throtl_grp *tg = pd_to_tg(pd);

610
	del_timer_sync(&tg->service_queue.pending_timer);
611
	kfree(tg);
612 613
}

614 615
static struct throtl_grp *
throtl_rb_first(struct throtl_service_queue *parent_sq)
616 617
{
	/* Service tree is empty */
618
	if (!parent_sq->nr_pending)
619 620
		return NULL;

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

624 625
	if (parent_sq->first_pending)
		return rb_entry_tg(parent_sq->first_pending);
626 627 628 629 630 631 632 633 634 635

	return NULL;
}

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

636 637
static void throtl_rb_erase(struct rb_node *n,
			    struct throtl_service_queue *parent_sq)
638
{
639 640 641 642
	if (parent_sq->first_pending == n)
		parent_sq->first_pending = NULL;
	rb_erase_init(n, &parent_sq->pending_tree);
	--parent_sq->nr_pending;
643 644
}

645
static void update_min_dispatch_time(struct throtl_service_queue *parent_sq)
646 647 648
{
	struct throtl_grp *tg;

649
	tg = throtl_rb_first(parent_sq);
650 651 652
	if (!tg)
		return;

653
	parent_sq->first_pending_disptime = tg->disptime;
654 655
}

656
static void tg_service_queue_add(struct throtl_grp *tg)
657
{
658
	struct throtl_service_queue *parent_sq = tg->service_queue.parent_sq;
659
	struct rb_node **node = &parent_sq->pending_tree.rb_node;
660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677
	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)
678
		parent_sq->first_pending = &tg->rb_node;
679 680

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

684
static void __throtl_enqueue_tg(struct throtl_grp *tg)
685
{
686
	tg_service_queue_add(tg);
687
	tg->flags |= THROTL_TG_PENDING;
688
	tg->service_queue.parent_sq->nr_pending++;
689 690
}

691
static void throtl_enqueue_tg(struct throtl_grp *tg)
692
{
693
	if (!(tg->flags & THROTL_TG_PENDING))
694
		__throtl_enqueue_tg(tg);
695 696
}

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

703
static void throtl_dequeue_tg(struct throtl_grp *tg)
704
{
705
	if (tg->flags & THROTL_TG_PENDING)
706
		__throtl_dequeue_tg(tg);
707 708
}

709
/* Call with queue lock held */
710 711
static void throtl_schedule_pending_timer(struct throtl_service_queue *sq,
					  unsigned long expires)
712
{
713
	unsigned long max_expire = jiffies + 8 * sq_to_td(sq)->throtl_slice;
714 715 716 717 718 719 720 721 722 723

	/*
	 * 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;
724 725 726
	mod_timer(&sq->pending_timer, expires);
	throtl_log(sq, "schedule timer. delay=%lu jiffies=%lu",
		   expires - jiffies, jiffies);
727 728
}

729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748
/**
 * throtl_schedule_next_dispatch - schedule the next dispatch cycle
 * @sq: the service_queue to schedule dispatch for
 * @force: force scheduling
 *
 * Arm @sq->pending_timer so that the next dispatch cycle starts on the
 * dispatch time of the first pending child.  Returns %true if either timer
 * is armed or there's no pending child left.  %false if the current
 * dispatch window is still open and the caller should continue
 * dispatching.
 *
 * If @force is %true, the dispatch timer is always scheduled and this
 * function is guaranteed to return %true.  This is to be used when the
 * caller can't dispatch itself and needs to invoke pending_timer
 * unconditionally.  Note that forced scheduling is likely to induce short
 * delay before dispatch starts even if @sq->first_pending_disptime is not
 * in the future and thus shouldn't be used in hot paths.
 */
static bool throtl_schedule_next_dispatch(struct throtl_service_queue *sq,
					  bool force)
749
{
750
	/* any pending children left? */
751
	if (!sq->nr_pending)
752
		return true;
753

754
	update_min_dispatch_time(sq);
755

756
	/* is the next dispatch time in the future? */
757
	if (force || time_after(sq->first_pending_disptime, jiffies)) {
758
		throtl_schedule_pending_timer(sq, sq->first_pending_disptime);
759
		return true;
760 761
	}

762 763
	/* tell the caller to continue dispatching */
	return false;
764 765
}

766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
static inline void throtl_start_new_slice_with_credit(struct throtl_grp *tg,
		bool rw, unsigned long start)
{
	tg->bytes_disp[rw] = 0;
	tg->io_disp[rw] = 0;

	/*
	 * Previous slice has expired. We must have trimmed it after last
	 * bio dispatch. That means since start of last slice, we never used
	 * that bandwidth. Do try to make use of that bandwidth while giving
	 * credit.
	 */
	if (time_after_eq(start, tg->slice_start[rw]))
		tg->slice_start[rw] = start;

781
	tg->slice_end[rw] = jiffies + tg->td->throtl_slice;
782 783 784 785 786 787
	throtl_log(&tg->service_queue,
		   "[%c] new slice with credit start=%lu end=%lu jiffies=%lu",
		   rw == READ ? 'R' : 'W', tg->slice_start[rw],
		   tg->slice_end[rw], jiffies);
}

788
static inline void throtl_start_new_slice(struct throtl_grp *tg, bool rw)
789 790
{
	tg->bytes_disp[rw] = 0;
791
	tg->io_disp[rw] = 0;
792
	tg->slice_start[rw] = jiffies;
793
	tg->slice_end[rw] = jiffies + tg->td->throtl_slice;
794 795 796 797
	throtl_log(&tg->service_queue,
		   "[%c] new slice start=%lu end=%lu jiffies=%lu",
		   rw == READ ? 'R' : 'W', tg->slice_start[rw],
		   tg->slice_end[rw], jiffies);
798 799
}

800 801
static inline void throtl_set_slice_end(struct throtl_grp *tg, bool rw,
					unsigned long jiffy_end)
802
{
803
	tg->slice_end[rw] = roundup(jiffy_end, tg->td->throtl_slice);
804 805
}

806 807
static inline void throtl_extend_slice(struct throtl_grp *tg, bool rw,
				       unsigned long jiffy_end)
808
{
809
	tg->slice_end[rw] = roundup(jiffy_end, tg->td->throtl_slice);
810 811 812 813
	throtl_log(&tg->service_queue,
		   "[%c] extend slice start=%lu end=%lu jiffies=%lu",
		   rw == READ ? 'R' : 'W', tg->slice_start[rw],
		   tg->slice_end[rw], jiffies);
814 815 816
}

/* Determine if previously allocated or extended slice is complete or not */
817
static bool throtl_slice_used(struct throtl_grp *tg, bool rw)
818 819
{
	if (time_in_range(jiffies, tg->slice_start[rw], tg->slice_end[rw]))
820
		return false;
821

822
	return true;
823 824 825
}

/* Trim the used slices and adjust slice start accordingly */
826
static inline void throtl_trim_slice(struct throtl_grp *tg, bool rw)
827
{
828 829
	unsigned long nr_slices, time_elapsed, io_trim;
	u64 bytes_trim, tmp;
830 831 832 833 834 835 836 837

	BUG_ON(time_before(tg->slice_end[rw], tg->slice_start[rw]));

	/*
	 * If bps are unlimited (-1), then time slice don't get
	 * renewed. Don't try to trim the slice if slice is used. A new
	 * slice will start when appropriate.
	 */
838
	if (throtl_slice_used(tg, rw))
839 840
		return;

841 842 843 844 845 846 847 848
	/*
	 * A bio has been dispatched. Also adjust slice_end. It might happen
	 * that initially cgroup limit was very low resulting in high
	 * slice_end, but later limit was bumped up and bio was dispached
	 * sooner, then we need to reduce slice_end. A high bogus slice_end
	 * is bad because it does not allow new slice to start.
	 */

849
	throtl_set_slice_end(tg, rw, jiffies + tg->td->throtl_slice);
850

851 852
	time_elapsed = jiffies - tg->slice_start[rw];

853
	nr_slices = time_elapsed / tg->td->throtl_slice;
854 855 856

	if (!nr_slices)
		return;
857
	tmp = tg_bps_limit(tg, rw) * tg->td->throtl_slice * nr_slices;
858 859
	do_div(tmp, HZ);
	bytes_trim = tmp;
860

861 862
	io_trim = (tg_iops_limit(tg, rw) * tg->td->throtl_slice * nr_slices) /
		HZ;
863

864
	if (!bytes_trim && !io_trim)
865 866 867 868 869 870 871
		return;

	if (tg->bytes_disp[rw] >= bytes_trim)
		tg->bytes_disp[rw] -= bytes_trim;
	else
		tg->bytes_disp[rw] = 0;

872 873 874 875 876
	if (tg->io_disp[rw] >= io_trim)
		tg->io_disp[rw] -= io_trim;
	else
		tg->io_disp[rw] = 0;

877
	tg->slice_start[rw] += nr_slices * tg->td->throtl_slice;
878

879 880 881 882
	throtl_log(&tg->service_queue,
		   "[%c] trim slice nr=%lu bytes=%llu io=%lu start=%lu end=%lu jiffies=%lu",
		   rw == READ ? 'R' : 'W', nr_slices, bytes_trim, io_trim,
		   tg->slice_start[rw], tg->slice_end[rw], jiffies);
883 884
}

885 886
static bool tg_with_in_iops_limit(struct throtl_grp *tg, struct bio *bio,
				  unsigned long *wait)
887 888
{
	bool rw = bio_data_dir(bio);
889
	unsigned int io_allowed;
890
	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
891
	u64 tmp;
892

893
	jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
894

895 896
	/* Slice has just started. Consider one slice interval */
	if (!jiffy_elapsed)
897
		jiffy_elapsed_rnd = tg->td->throtl_slice;
898

899
	jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, tg->td->throtl_slice);
900

901 902 903 904 905 906 907
	/*
	 * jiffy_elapsed_rnd should not be a big value as minimum iops can be
	 * 1 then at max jiffy elapsed should be equivalent of 1 second as we
	 * will allow dispatch after 1 second and after that slice should
	 * have been trimmed.
	 */

908
	tmp = (u64)tg_iops_limit(tg, rw) * jiffy_elapsed_rnd;
909 910 911 912 913 914
	do_div(tmp, HZ);

	if (tmp > UINT_MAX)
		io_allowed = UINT_MAX;
	else
		io_allowed = tmp;
915 916

	if (tg->io_disp[rw] + 1 <= io_allowed) {
917 918
		if (wait)
			*wait = 0;
919
		return true;
920 921
	}

922
	/* Calc approx time to dispatch */
923
	jiffy_wait = ((tg->io_disp[rw] + 1) * HZ) / tg_iops_limit(tg, rw) + 1;
924 925 926 927 928 929 930 931

	if (jiffy_wait > jiffy_elapsed)
		jiffy_wait = jiffy_wait - jiffy_elapsed;
	else
		jiffy_wait = 1;

	if (wait)
		*wait = jiffy_wait;
932
	return false;
933 934
}

935 936
static bool tg_with_in_bps_limit(struct throtl_grp *tg, struct bio *bio,
				 unsigned long *wait)
937 938
{
	bool rw = bio_data_dir(bio);
939
	u64 bytes_allowed, extra_bytes, tmp;
940
	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
941
	unsigned int bio_size = throtl_bio_data_size(bio);
942 943 944 945 946

	jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];

	/* Slice has just started. Consider one slice interval */
	if (!jiffy_elapsed)
947
		jiffy_elapsed_rnd = tg->td->throtl_slice;
948

949
	jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, tg->td->throtl_slice);
950

951
	tmp = tg_bps_limit(tg, rw) * jiffy_elapsed_rnd;
952
	do_div(tmp, HZ);
953
	bytes_allowed = tmp;
954

955
	if (tg->bytes_disp[rw] + bio_size <= bytes_allowed) {
956 957
		if (wait)
			*wait = 0;
958
		return true;
959 960 961
	}

	/* Calc approx time to dispatch */
962
	extra_bytes = tg->bytes_disp[rw] + bio_size - bytes_allowed;
963
	jiffy_wait = div64_u64(extra_bytes * HZ, tg_bps_limit(tg, rw));
964 965 966 967 968 969 970 971 972 973 974

	if (!jiffy_wait)
		jiffy_wait = 1;

	/*
	 * This wait time is without taking into consideration the rounding
	 * up we did. Add that time also.
	 */
	jiffy_wait = jiffy_wait + (jiffy_elapsed_rnd - jiffy_elapsed);
	if (wait)
		*wait = jiffy_wait;
975
	return false;
976 977 978 979 980 981
}

/*
 * Returns whether one can dispatch a bio or not. Also returns approx number
 * of jiffies to wait before this bio is with-in IO rate and can be dispatched
 */
982 983
static bool tg_may_dispatch(struct throtl_grp *tg, struct bio *bio,
			    unsigned long *wait)
984 985 986 987 988 989 990 991 992 993
{
	bool rw = bio_data_dir(bio);
	unsigned long bps_wait = 0, iops_wait = 0, max_wait = 0;

	/*
 	 * Currently whole state machine of group depends on first bio
	 * queued in the group bio list. So one should not be calling
	 * this function with a different bio if there are other bios
	 * queued.
	 */
994
	BUG_ON(tg->service_queue.nr_queued[rw] &&
995
	       bio != throtl_peek_queued(&tg->service_queue.queued[rw]));
996

997
	/* If tg->bps = -1, then BW is unlimited */
998 999
	if (tg_bps_limit(tg, rw) == U64_MAX &&
	    tg_iops_limit(tg, rw) == UINT_MAX) {
1000 1001
		if (wait)
			*wait = 0;
1002
		return true;
1003 1004 1005 1006 1007
	}

	/*
	 * If previous slice expired, start a new one otherwise renew/extend
	 * existing slice to make sure it is at least throtl_slice interval
1008 1009 1010
	 * long since now. New slice is started only for empty throttle group.
	 * If there is queued bio, that means there should be an active
	 * slice and it should be extended instead.
1011
	 */
1012
	if (throtl_slice_used(tg, rw) && !(tg->service_queue.nr_queued[rw]))
1013
		throtl_start_new_slice(tg, rw);
1014
	else {
1015 1016 1017 1018
		if (time_before(tg->slice_end[rw],
		    jiffies + tg->td->throtl_slice))
			throtl_extend_slice(tg, rw,
				jiffies + tg->td->throtl_slice);
1019 1020
	}

1021 1022
	if (tg_with_in_bps_limit(tg, bio, &bps_wait) &&
	    tg_with_in_iops_limit(tg, bio, &iops_wait)) {
1023 1024
		if (wait)
			*wait = 0;
1025
		return true;
1026 1027 1028 1029 1030 1031 1032 1033
	}

	max_wait = max(bps_wait, iops_wait);

	if (wait)
		*wait = max_wait;

	if (time_before(tg->slice_end[rw], jiffies + max_wait))
1034
		throtl_extend_slice(tg, rw, jiffies + max_wait);
1035

1036
	return false;
1037 1038 1039 1040 1041
}

static void throtl_charge_bio(struct throtl_grp *tg, struct bio *bio)
{
	bool rw = bio_data_dir(bio);
1042
	unsigned int bio_size = throtl_bio_data_size(bio);
1043 1044

	/* Charge the bio to the group */
1045
	tg->bytes_disp[rw] += bio_size;
1046
	tg->io_disp[rw]++;
1047
	tg->last_bytes_disp[rw] += bio_size;
1048
	tg->last_io_disp[rw]++;
1049

1050
	/*
1051
	 * BIO_THROTTLED is used to prevent the same bio to be throttled
1052 1053 1054 1055
	 * more than once as a throttled bio will go through blk-throtl the
	 * second time when it eventually gets issued.  Set it when a bio
	 * is being charged to a tg.
	 */
1056 1057
	if (!bio_flagged(bio, BIO_THROTTLED))
		bio_set_flag(bio, BIO_THROTTLED);
1058 1059
}

1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
/**
 * throtl_add_bio_tg - add a bio to the specified throtl_grp
 * @bio: bio to add
 * @qn: qnode to use
 * @tg: the target throtl_grp
 *
 * Add @bio to @tg's service_queue using @qn.  If @qn is not specified,
 * tg->qnode_on_self[] is used.
 */
static void throtl_add_bio_tg(struct bio *bio, struct throtl_qnode *qn,
			      struct throtl_grp *tg)
1071
{
1072
	struct throtl_service_queue *sq = &tg->service_queue;
1073 1074
	bool rw = bio_data_dir(bio);

1075 1076 1077
	if (!qn)
		qn = &tg->qnode_on_self[rw];

1078 1079 1080 1081 1082 1083 1084 1085 1086
	/*
	 * If @tg doesn't currently have any bios queued in the same
	 * direction, queueing @bio can change when @tg should be
	 * dispatched.  Mark that @tg was empty.  This is automatically
	 * cleaered on the next tg_update_disptime().
	 */
	if (!sq->nr_queued[rw])
		tg->flags |= THROTL_TG_WAS_EMPTY;

1087 1088
	throtl_qnode_add_bio(bio, qn, &sq->queued[rw]);

1089
	sq->nr_queued[rw]++;
1090
	throtl_enqueue_tg(tg);
1091 1092
}

1093
static void tg_update_disptime(struct throtl_grp *tg)
1094
{
1095
	struct throtl_service_queue *sq = &tg->service_queue;
1096 1097 1098
	unsigned long read_wait = -1, write_wait = -1, min_wait = -1, disptime;
	struct bio *bio;

1099 1100
	bio = throtl_peek_queued(&sq->queued[READ]);
	if (bio)
1101
		tg_may_dispatch(tg, bio, &read_wait);
1102

1103 1104
	bio = throtl_peek_queued(&sq->queued[WRITE]);
	if (bio)
1105
		tg_may_dispatch(tg, bio, &write_wait);
1106 1107 1108 1109 1110

	min_wait = min(read_wait, write_wait);
	disptime = jiffies + min_wait;

	/* Update dispatch time */
1111
	throtl_dequeue_tg(tg);
1112
	tg->disptime = disptime;
1113
	throtl_enqueue_tg(tg);
1114 1115 1116

	/* see throtl_add_bio_tg() */
	tg->flags &= ~THROTL_TG_WAS_EMPTY;
1117 1118
}

1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
static void start_parent_slice_with_credit(struct throtl_grp *child_tg,
					struct throtl_grp *parent_tg, bool rw)
{
	if (throtl_slice_used(parent_tg, rw)) {
		throtl_start_new_slice_with_credit(parent_tg, rw,
				child_tg->slice_start[rw]);
	}

}

1129
static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
1130
{
1131
	struct throtl_service_queue *sq = &tg->service_queue;
1132 1133
	struct throtl_service_queue *parent_sq = sq->parent_sq;
	struct throtl_grp *parent_tg = sq_to_tg(parent_sq);
1134
	struct throtl_grp *tg_to_put = NULL;
1135 1136
	struct bio *bio;

1137 1138 1139 1140 1141 1142 1143
	/*
	 * @bio is being transferred from @tg to @parent_sq.  Popping a bio
	 * from @tg may put its reference and @parent_sq might end up
	 * getting released prematurely.  Remember the tg to put and put it
	 * after @bio is transferred to @parent_sq.
	 */
	bio = throtl_pop_queued(&sq->queued[rw], &tg_to_put);
1144
	sq->nr_queued[rw]--;
1145 1146

	throtl_charge_bio(tg, bio);
1147 1148 1149 1150 1151 1152 1153 1154 1155

	/*
	 * If our parent is another tg, we just need to transfer @bio to
	 * the parent using throtl_add_bio_tg().  If our parent is
	 * @td->service_queue, @bio is ready to be issued.  Put it on its
	 * bio_lists[] and decrease total number queued.  The caller is
	 * responsible for issuing these bios.
	 */
	if (parent_tg) {
1156
		throtl_add_bio_tg(bio, &tg->qnode_on_parent[rw], parent_tg);
1157
		start_parent_slice_with_credit(tg, parent_tg, rw);
1158
	} else {
1159 1160
		throtl_qnode_add_bio(bio, &tg->qnode_on_parent[rw],
				     &parent_sq->queued[rw]);
1161 1162 1163
		BUG_ON(tg->td->nr_queued[rw] <= 0);
		tg->td->nr_queued[rw]--;
	}
1164

1165
	throtl_trim_slice(tg, rw);
1166

1167 1168
	if (tg_to_put)
		blkg_put(tg_to_blkg(tg_to_put));
1169 1170
}

1171
static int throtl_dispatch_tg(struct throtl_grp *tg)
1172
{
1173
	struct throtl_service_queue *sq = &tg->service_queue;
1174 1175
	unsigned int nr_reads = 0, nr_writes = 0;
	unsigned int max_nr_reads = throtl_grp_quantum*3/4;
1176
	unsigned int max_nr_writes = throtl_grp_quantum - max_nr_reads;
1177 1178 1179 1180
	struct bio *bio;

	/* Try to dispatch 75% READS and 25% WRITES */

1181
	while ((bio = throtl_peek_queued(&sq->queued[READ])) &&
1182
	       tg_may_dispatch(tg, bio, NULL)) {