blk-throttle.c 73.0 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

T
Tejun Heo 已提交
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 {
S
Shaohua Li 已提交
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];

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

S
Shaohua Li 已提交
148
	/* internally used IOPS limits */
149
	unsigned int iops[2][LIMIT_CNT];
S
Shaohua Li 已提交
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

S
Shaohua Li 已提交
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

	/* total time spent on lower layer: scheduler, device and others */
	struct blkg_rwstat service_time;
	/* total time spent on block throttle */
	struct blkg_rwstat wait_time;
185 186 187 188
	/* total bytes throttled */
	struct blkg_rwstat total_bytes_queued;
	/* total IOs throttled */
	struct blkg_rwstat total_io_queued;
189 190
};

191 192 193 194 195 196 197 198 199 200 201 202 203
/* 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;
};

204 205 206
struct throtl_data
{
	/* service tree for active throtl groups */
207
	struct throtl_service_queue service_queue;
208 209 210 211 212 213

	struct request_queue *queue;

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

214 215
	unsigned int throtl_slice;

216
	/* Work for dispatching throttled bios */
217
	struct work_struct dispatch_work;
218 219
	unsigned int limit_index;
	bool limit_valid[LIMIT_CNT];
S
Shaohua Li 已提交
220 221 222

	unsigned long low_upgrade_time;
	unsigned long low_downgrade_time;
223 224

	unsigned int scale;
225

226 227 228
	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];
229
	unsigned long last_calculate_time;
230
	unsigned long filtered_latency;
231 232

	bool track_bio_latency;
233 234
};

235
static void throtl_pending_timer_fn(struct timer_list *t);
236

237 238 239 240 241
static inline struct throtl_grp *pd_to_tg(struct blkg_policy_data *pd)
{
	return pd ? container_of(pd, struct throtl_grp, pd) : NULL;
}

T
Tejun Heo 已提交
242
static inline struct throtl_grp *blkg_to_tg(struct blkcg_gq *blkg)
243
{
244
	return pd_to_tg(blkg_to_pd(blkg, &blkcg_policy_throtl));
245 246
}

T
Tejun Heo 已提交
247
static inline struct blkcg_gq *tg_to_blkg(struct throtl_grp *tg)
248
{
249
	return pd_to_blkg(&tg->pd);
250 251
}

252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
/**
 * 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
 *
271
 * A service_queue can be embedded in either a throtl_grp or throtl_data.
272 273 274 275 276 277 278 279 280 281 282 283
 * 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);
}

284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
/*
 * 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;
}

302 303
static uint64_t tg_bps_limit(struct throtl_grp *tg, int rw)
{
304
	struct blkcg_gq *blkg = tg_to_blkg(tg);
305
	struct throtl_data *td;
306 307 308 309
	uint64_t ret;

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

	td = tg->td;
	ret = tg->bps[rw][td->limit_index];
313 314 315 316 317 318 319 320
	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;
	}
321 322 323 324 325 326 327 328

	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);
	}
329
	return ret;
330 331 332 333
}

static unsigned int tg_iops_limit(struct throtl_grp *tg, int rw)
{
334
	struct blkcg_gq *blkg = tg_to_blkg(tg);
335
	struct throtl_data *td;
336 337 338 339
	unsigned int ret;

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

341 342
	td = tg->td;
	ret = tg->iops[rw][td->limit_index];
343 344 345 346 347 348 349 350
	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;
	}
351 352 353 354 355 356 357 358 359 360

	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);
	}
361
	return ret;
362 363
}

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

367 368 369 370 371 372 373 374 375 376 377 378 379 380
/**
 * 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;							\
381 382
	if (likely(!blk_trace_note_message_enabled(__td->queue)))	\
		break;							\
383
	if ((__tg)) {							\
384 385
		blk_add_cgroup_trace_msg(__td->queue,			\
			tg_to_blkg(__tg)->blkcg, "throtl " fmt, ##args);\
386 387 388
	} else {							\
		blk_add_trace_msg(__td->queue, "throtl " fmt, ##args);	\
	}								\
T
Tejun Heo 已提交
389
} while (0)
390

391 392 393 394 395 396 397 398
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;
}

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 473 474 475 476 477 478 479 480 481
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;
}

482
/* init a service_queue, assumes the caller zeroed it */
483
static void throtl_service_queue_init(struct throtl_service_queue *sq)
484
{
485 486
	INIT_LIST_HEAD(&sq->queued[0]);
	INIT_LIST_HEAD(&sq->queued[1]);
487
	sq->pending_tree = RB_ROOT;
488
	timer_setup(&sq->pending_timer, throtl_pending_timer_fn, 0);
489 490
}

491 492 493
static struct blkg_policy_data *throtl_pd_alloc(gfp_t gfp,
						struct request_queue *q,
						struct blkcg *blkcg)
494
{
495
	struct throtl_grp *tg;
T
Tejun Heo 已提交
496
	int rw;
497

498
	tg = kzalloc_node(sizeof(*tg), gfp, q->node);
499
	if (!tg)
500
		return NULL;
501

502
	if (blkg_rwstat_init(&tg->service_time, gfp) ||
503 504 505
	    blkg_rwstat_init(&tg->wait_time, gfp) ||
	    blkg_rwstat_init(&tg->total_bytes_queued, gfp) ||
	    blkg_rwstat_init(&tg->total_io_queued, gfp))
506 507
		goto err;

508 509 510 511 512 513 514 515
	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);
516 517 518 519
	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;
S
Shaohua Li 已提交
520 521 522 523 524
	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 */
525

526
	tg->latency_target = DFL_LATENCY_TARGET;
527
	tg->latency_target_conf = DFL_LATENCY_TARGET;
528 529
	tg->idletime_threshold = DFL_IDLE_THRESHOLD;
	tg->idletime_threshold_conf = DFL_IDLE_THRESHOLD;
530

531
	return &tg->pd;
532 533 534 535

err:
	blkg_rwstat_exit(&tg->service_time);
	blkg_rwstat_exit(&tg->wait_time);
536 537
	blkg_rwstat_exit(&tg->total_bytes_queued);
	blkg_rwstat_exit(&tg->total_io_queued);
538 539
	kfree(tg);
	return NULL;
540 541
}

542
static void throtl_pd_init(struct blkg_policy_data *pd)
543
{
544 545
	struct throtl_grp *tg = pd_to_tg(pd);
	struct blkcg_gq *blkg = tg_to_blkg(tg);
546
	struct throtl_data *td = blkg->q->td;
547
	struct throtl_service_queue *sq = &tg->service_queue;
548

549
	/*
550
	 * If on the default hierarchy, we switch to properly hierarchical
551 552 553 554 555
	 * 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.
	 *
556
	 * If not on the default hierarchy, the broken flat hierarchy
557 558 559 560 561
	 * 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.
	 */
562
	sq->parent_sq = &td->service_queue;
563 564 565

	/* Enable hierarchical throttling even on traditional hierarchy */
	if (blkg->parent)
566
		sq->parent_sq = &blkg_to_tg(blkg->parent)->service_queue;
567
	tg->td = td;
568 569
}

570 571 572 573 574 575 576 577
/*
 * 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);
578
	struct throtl_data *td = tg->td;
579 580 581 582
	int rw;

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

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

S
Shaohua Li 已提交
598 599 600 601 602 603 604 605 606 607 608
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] ||
609
		    tg->iops[READ][LIMIT_LOW] || tg->iops[WRITE][LIMIT_LOW]) {
S
Shaohua Li 已提交
610
			low_valid = true;
611 612
			break;
		}
S
Shaohua Li 已提交
613 614 615 616 617 618
	}
	rcu_read_unlock();

	td->limit_valid[LIMIT_LOW] = low_valid;
}

619
static void throtl_upgrade_state(struct throtl_data *td);
S
Shaohua Li 已提交
620 621 622
static void throtl_pd_offline(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);
623 624
	struct blkcg_gq *blkg = pd_to_blkg(pd);
	struct blkcg_gq *parent = blkg->parent;
S
Shaohua Li 已提交
625 626 627 628 629 630 631 632

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

633 634
	if (!tg->td->limit_valid[tg->td->limit_index])
		throtl_upgrade_state(tg->td);
635 636 637 638 639
	if (parent) {
		blkg_rwstat_add_aux(&blkg_to_tg(parent)->service_time,
				    &tg->service_time);
		blkg_rwstat_add_aux(&blkg_to_tg(parent)->wait_time,
				    &tg->wait_time);
640 641 642 643
		blkg_rwstat_add_aux(&blkg_to_tg(parent)->total_bytes_queued,
				    &tg->total_bytes_queued);
		blkg_rwstat_add_aux(&blkg_to_tg(parent)->total_io_queued,
				    &tg->total_io_queued);
644
	}
S
Shaohua Li 已提交
645 646
}

647 648
static void throtl_pd_free(struct blkg_policy_data *pd)
{
649 650
	struct throtl_grp *tg = pd_to_tg(pd);

651
	del_timer_sync(&tg->service_queue.pending_timer);
652 653
	blkg_rwstat_exit(&tg->service_time);
	blkg_rwstat_exit(&tg->wait_time);
654 655
	blkg_rwstat_exit(&tg->total_bytes_queued);
	blkg_rwstat_exit(&tg->total_io_queued);
656
	kfree(tg);
657 658
}

659 660 661 662 663 664
static void throtl_pd_reset(struct blkg_policy_data *pd)
{
	struct throtl_grp *tg = pd_to_tg(pd);

	blkg_rwstat_reset(&tg->service_time);
	blkg_rwstat_reset(&tg->wait_time);
665 666
	blkg_rwstat_reset(&tg->total_bytes_queued);
	blkg_rwstat_reset(&tg->total_io_queued);
667 668
}

669 670
static struct throtl_grp *
throtl_rb_first(struct throtl_service_queue *parent_sq)
671 672
{
	/* Service tree is empty */
673
	if (!parent_sq->nr_pending)
674 675
		return NULL;

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

679 680
	if (parent_sq->first_pending)
		return rb_entry_tg(parent_sq->first_pending);
681 682 683 684 685 686 687 688 689 690

	return NULL;
}

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

691 692
static void throtl_rb_erase(struct rb_node *n,
			    struct throtl_service_queue *parent_sq)
693
{
694 695 696 697
	if (parent_sq->first_pending == n)
		parent_sq->first_pending = NULL;
	rb_erase_init(n, &parent_sq->pending_tree);
	--parent_sq->nr_pending;
698 699
}

700
static void update_min_dispatch_time(struct throtl_service_queue *parent_sq)
701 702 703
{
	struct throtl_grp *tg;

704
	tg = throtl_rb_first(parent_sq);
705 706 707
	if (!tg)
		return;

708
	parent_sq->first_pending_disptime = tg->disptime;
709 710
}

711
static void tg_service_queue_add(struct throtl_grp *tg)
712
{
713
	struct throtl_service_queue *parent_sq = tg->service_queue.parent_sq;
714
	struct rb_node **node = &parent_sq->pending_tree.rb_node;
715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732
	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)
733
		parent_sq->first_pending = &tg->rb_node;
734 735

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

739
static void __throtl_enqueue_tg(struct throtl_grp *tg)
740
{
741
	tg_service_queue_add(tg);
742
	tg->flags |= THROTL_TG_PENDING;
743
	tg->service_queue.parent_sq->nr_pending++;
744 745
}

746
static void throtl_enqueue_tg(struct throtl_grp *tg)
747
{
748
	if (!(tg->flags & THROTL_TG_PENDING))
749
		__throtl_enqueue_tg(tg);
750 751
}

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

758
static void throtl_dequeue_tg(struct throtl_grp *tg)
759
{
760
	if (tg->flags & THROTL_TG_PENDING)
761
		__throtl_dequeue_tg(tg);
762 763
}

764
/* Call with queue lock held */
765 766
static void throtl_schedule_pending_timer(struct throtl_service_queue *sq,
					  unsigned long expires)
767
{
768
	unsigned long max_expire = jiffies + 8 * sq_to_td(sq)->throtl_slice;
769 770 771 772 773 774 775 776 777 778

	/*
	 * 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;
779 780 781
	mod_timer(&sq->pending_timer, expires);
	throtl_log(sq, "schedule timer. delay=%lu jiffies=%lu",
		   expires - jiffies, jiffies);
782 783
}

784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803
/**
 * 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)
804
{
805
	/* any pending children left? */
806
	if (!sq->nr_pending)
807
		return true;
808

809
	update_min_dispatch_time(sq);
810

811
	/* is the next dispatch time in the future? */
812
	if (force || time_after(sq->first_pending_disptime, jiffies)) {
813
		throtl_schedule_pending_timer(sq, sq->first_pending_disptime);
814
		return true;
815 816
	}

817 818
	/* tell the caller to continue dispatching */
	return false;
819 820
}

821 822 823 824 825 826 827 828 829 830 831 832 833 834 835
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;

836
	tg->slice_end[rw] = jiffies + tg->td->throtl_slice;
837 838 839 840 841 842
	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);
}

843
static inline void throtl_start_new_slice(struct throtl_grp *tg, bool rw)
844 845
{
	tg->bytes_disp[rw] = 0;
846
	tg->io_disp[rw] = 0;
847
	tg->slice_start[rw] = jiffies;
848
	tg->slice_end[rw] = jiffies + tg->td->throtl_slice;
849 850 851 852
	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);
853 854
}

855 856
static inline void throtl_set_slice_end(struct throtl_grp *tg, bool rw,
					unsigned long jiffy_end)
857
{
858
	tg->slice_end[rw] = roundup(jiffy_end, tg->td->throtl_slice);
859 860
}

861 862
static inline void throtl_extend_slice(struct throtl_grp *tg, bool rw,
				       unsigned long jiffy_end)
863
{
864
	tg->slice_end[rw] = roundup(jiffy_end, tg->td->throtl_slice);
865 866 867 868
	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);
869 870 871
}

/* Determine if previously allocated or extended slice is complete or not */
872
static bool throtl_slice_used(struct throtl_grp *tg, bool rw)
873 874
{
	if (time_in_range(jiffies, tg->slice_start[rw], tg->slice_end[rw]))
875
		return false;
876

877
	return true;
878 879 880
}

/* Trim the used slices and adjust slice start accordingly */
881
static inline void throtl_trim_slice(struct throtl_grp *tg, bool rw)
882
{
883 884
	unsigned long nr_slices, time_elapsed, io_trim;
	u64 bytes_trim, tmp;
885 886 887 888 889 890 891 892

	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.
	 */
893
	if (throtl_slice_used(tg, rw))
894 895
		return;

896 897 898 899 900 901 902 903
	/*
	 * 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.
	 */

904
	throtl_set_slice_end(tg, rw, jiffies + tg->td->throtl_slice);
905

906 907
	time_elapsed = jiffies - tg->slice_start[rw];

908
	nr_slices = time_elapsed / tg->td->throtl_slice;
909 910 911

	if (!nr_slices)
		return;
912
	tmp = tg_bps_limit(tg, rw) * tg->td->throtl_slice * nr_slices;
913 914
	do_div(tmp, HZ);
	bytes_trim = tmp;
915

916 917
	io_trim = (tg_iops_limit(tg, rw) * tg->td->throtl_slice * nr_slices) /
		HZ;
918

919
	if (!bytes_trim && !io_trim)
920 921 922 923 924 925 926
		return;

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

927 928 929 930 931
	if (tg->io_disp[rw] >= io_trim)
		tg->io_disp[rw] -= io_trim;
	else
		tg->io_disp[rw] = 0;

932
	tg->slice_start[rw] += nr_slices * tg->td->throtl_slice;
933

934 935 936 937
	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);
938 939
}

940 941
static bool tg_with_in_iops_limit(struct throtl_grp *tg, struct bio *bio,
				  unsigned long *wait)
942 943
{
	bool rw = bio_data_dir(bio);
944
	unsigned int io_allowed;
945
	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
946
	u64 tmp;
947

948
	jiffy_elapsed = jiffies - tg->slice_start[rw];
949

950 951
	/* Round up to the next throttle slice, wait time must be nonzero */
	jiffy_elapsed_rnd = roundup(jiffy_elapsed + 1, tg->td->throtl_slice);
952

953 954 955 956 957 958 959
	/*
	 * 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.
	 */

960
	tmp = (u64)tg_iops_limit(tg, rw) * jiffy_elapsed_rnd;
961 962 963 964 965 966
	do_div(tmp, HZ);

	if (tmp > UINT_MAX)
		io_allowed = UINT_MAX;
	else
		io_allowed = tmp;
967 968

	if (tg->io_disp[rw] + 1 <= io_allowed) {
969 970
		if (wait)
			*wait = 0;
971
		return true;
972 973
	}

974
	/* Calc approx time to dispatch */
975
	jiffy_wait = jiffy_elapsed_rnd - jiffy_elapsed;
976 977 978

	if (wait)
		*wait = jiffy_wait;
979
	return false;
980 981
}

982 983
static bool tg_with_in_bps_limit(struct throtl_grp *tg, struct bio *bio,
				 unsigned long *wait)
984 985
{
	bool rw = bio_data_dir(bio);
986
	u64 bytes_allowed, extra_bytes, tmp;
987
	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
988
	unsigned int bio_size = throtl_bio_data_size(bio);
989 990 991 992 993

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

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

996
	jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, tg->td->throtl_slice);
997

998
	tmp = tg_bps_limit(tg, rw) * jiffy_elapsed_rnd;
999
	do_div(tmp, HZ);
1000
	bytes_allowed = tmp;
1001

1002
	if (tg->bytes_disp[rw] + bio_size <= bytes_allowed) {
1003 1004
		if (wait)
			*wait = 0;
1005
		return true;
1006 1007 1008
	}

	/* Calc approx time to dispatch */
1009
	extra_bytes = tg->bytes_disp[rw] + bio_size - bytes_allowed;
1010
	jiffy_wait = div64_u64(extra_bytes * HZ, tg_bps_limit(tg, rw));
1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021

	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;
1022
	return false;
1023 1024 1025 1026 1027 1028
}

/*
 * 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
 */
1029 1030
static bool tg_may_dispatch(struct throtl_grp *tg, struct bio *bio,
			    unsigned long *wait)
1031 1032 1033 1034 1035 1036 1037 1038 1039 1040
{
	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.
	 */
1041
	BUG_ON(tg->service_queue.nr_queued[rw] &&
1042
	       bio != throtl_peek_queued(&tg->service_queue.queued[rw]));
1043

1044
	/* If tg->bps = -1, then BW is unlimited */
1045 1046
	if (tg_bps_limit(tg, rw) == U64_MAX &&
	    tg_iops_limit(tg, rw) == UINT_MAX) {
1047 1048
		if (wait)
			*wait = 0;
1049
		return true;
1050 1051 1052 1053 1054
	}

	/*
	 * If previous slice expired, start a new one otherwise renew/extend
	 * existing slice to make sure it is at least throtl_slice interval
1055 1056 1057
	 * 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.
1058
	 */
1059
	if (throtl_slice_used(tg, rw) && !(tg->service_queue.nr_queued[rw]))
1060
		throtl_start_new_slice(tg, rw);
1061
	else {
1062 1063 1064 1065
		if (time_before(tg->slice_end[rw],
		    jiffies + tg->td->throtl_slice))
			throtl_extend_slice(tg, rw,
				jiffies + tg->td->throtl_slice);
1066 1067
	}

1068 1069
	if (tg_with_in_bps_limit(tg, bio, &bps_wait) &&
	    tg_with_in_iops_limit(tg, bio, &iops_wait)) {
1070 1071
		if (wait)
			*wait = 0;
1072
		return true;
1073 1074 1075 1076 1077 1078 1079 1080
	}

	max_wait = max(bps_wait, iops_wait);

	if (wait)
		*wait = max_wait;

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

1083
	return false;
1084 1085
}

1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
static void throtl_stats_update_completion(struct throtl_grp *tg,
					   uint64_t start_time,
					   uint64_t io_start_time,
					   int op)
{
	unsigned long flags;
	uint64_t now = sched_clock();

	local_irq_save(flags);
	if (time_after64(now, io_start_time))
		blkg_rwstat_add(&tg->service_time, op, now - io_start_time);
	if (time_after64(io_start_time, start_time))
		blkg_rwstat_add(&tg->wait_time, op, io_start_time - start_time);
	local_irq_restore(flags);
}

static void throtl_bio_end_io(struct bio *bio)
{
	struct throtl_grp *tg;

	rcu_read_lock();
1107 1108 1109 1110
	/* see comments in throtl_bio_stats_start() */
	if (bio_flagged(bio, BIO_THROTL_STATED))
		goto out;

1111 1112 1113 1114 1115 1116 1117 1118
	tg = (struct throtl_grp *)bio->bi_tg_private;
	if (!tg)
		goto out;

	throtl_stats_update_completion(tg, bio_start_time_ns(bio),
				       bio_io_start_time_ns(bio),
				       bio_op(bio));
	blkg_put(tg_to_blkg(tg));
1119
	bio_clear_flag(bio, BIO_THROTL_STATED);
1120 1121 1122 1123 1124 1125 1126 1127
out:
	rcu_read_unlock();
}

static inline void throtl_bio_stats_start(struct bio *bio, struct throtl_grp *tg)
{
	int op = bio_op(bio);

1128 1129 1130 1131 1132 1133 1134 1135 1136 1137
	/*
	 * It may happen that end_io will be called twice like dm-thin,
	 * which will save origin end_io first, and call its overwrite
	 * end_io and then the saved end_io. We use bio flag
	 * BIO_THROTL_STATED to do only once statistics.
	 */
	if ((op == REQ_OP_READ || op == REQ_OP_WRITE) &&
	    !bio_flagged(bio, BIO_THROTL_STATED)) {
		blkg_get(tg_to_blkg(tg));
		bio_set_flag(bio, BIO_THROTL_STATED);
1138 1139 1140 1141 1142 1143
		bio->bi_tg_end_io = throtl_bio_end_io;
		bio->bi_tg_private = tg;
		bio_set_start_time_ns(bio);
	}
}

1144 1145 1146
static void throtl_charge_bio(struct throtl_grp *tg, struct bio *bio)
{
	bool rw = bio_data_dir(bio);
1147
	unsigned int bio_size = throtl_bio_data_size(bio);
1148 1149

	/* Charge the bio to the group */
1150
	tg->bytes_disp[rw] += bio_size;
1151
	tg->io_disp[rw]++;
1152
	tg->last_bytes_disp[rw] += bio_size;
S
Shaohua Li 已提交
1153
	tg->last_io_disp[rw]++;
1154

1155
	/*
1156
	 * BIO_THROTTLED is used to prevent the same bio to be throttled
1157 1158 1159 1160
	 * 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.
	 */
1161 1162
	if (!bio_flagged(bio, BIO_THROTTLED))
		bio_set_flag(bio, BIO_THROTTLED);
1163 1164
}

1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175
/**
 * 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)
1176
{
1177
	struct throtl_service_queue *sq = &tg->service_queue;
1178 1179
	bool rw = bio_data_dir(bio);

1180 1181 1182
	if (!qn)
		qn = &tg->qnode_on_self[rw];

1183 1184 1185 1186 1187 1188 1189 1190 1191
	/*
	 * 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;

1192 1193
	throtl_qnode_add_bio(bio, qn, &sq->queued[rw]);

1194
	sq->nr_queued[rw]++;
1195 1196 1197
	blkg_rwstat_add(&tg->total_bytes_queued, bio_op(bio),
			throtl_bio_data_size(bio));
	blkg_rwstat_add(&tg->total_io_queued, bio_op(bio), 1);
1198
	throtl_enqueue_tg(tg);
1199 1200
}

1201
static void tg_update_disptime(struct throtl_grp *tg)
1202
{
1203
	struct throtl_service_queue *sq = &tg->service_queue;
1204 1205 1206
	unsigned long read_wait = -1, write_wait = -1, min_wait = -1, disptime;
	struct bio *bio;

1207 1208
	bio = throtl_peek_queued(&sq->queued[READ]);
	if (bio)
1209
		tg_may_dispatch(tg, bio, &read_wait);
1210

1211 1212
	bio = throtl_peek_queued(&sq->queued[WRITE]);
	if (bio)
1213
		tg_may_dispatch(tg, bio, &write_wait);
1214 1215 1216 1217 1218

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

	/* Update dispatch time */
1219
	throtl_dequeue_tg(tg);
1220
	tg->disptime = disptime;
1221
	throtl_enqueue_tg(tg);
1222 1223 1224

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

1227 1228 1229 1230 1231 1232 1233 1234 1235 1236
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]);
	}

}

1237
static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
1238
{
1239
	struct throtl_service_queue *sq = &tg->service_queue;
1240 1241
	struct throtl_service_queue *parent_sq = sq->parent_sq;
	struct throtl_grp *parent_tg = sq_to_tg(parent_sq);
1242
	struct throtl_grp *tg_to_put = NULL;
1243 1244
	struct bio *bio;

1245 1246 1247 1248 1249 1250 1251
	/*
	 * @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);
1252
	sq->nr_queued[rw]--;
1253 1254

	throtl_charge_bio(tg, bio);
1255 1256 1257 1258 1259 1260 1261 1262 1263

	/*
	 * 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) {
1264
		throtl_add_bio_tg(bio, &tg->qnode_on_parent[rw], parent_tg);
1265
		start_parent_slice_with_credit(tg, parent_tg, rw);
1266
	} else {
1267 1268
		throtl_qnode_add_bio(bio, &tg->qnode_on_parent[rw],
				     &parent_sq->queued[rw]);
1269 1270 1271
		BUG_ON(tg->td->nr_queued[rw] <= 0);
		tg->td->nr_queued[rw]--;
	}
1272

1273
	throtl_trim_slice(tg, rw);
1274

1275 1276
	if (tg_to_put)
		blkg_put(tg_to_blkg(tg_to_put));
1277 1278
}

1279
static int throtl_dispatch_tg(struct throtl_grp *tg)
1280
{
1281
	struct throtl_service_queue *sq = &tg->service_queue;
1282 1283
	unsigned int nr_reads = 0, nr_writes = 0;
	unsigned int max_nr_reads = throtl_grp_quantum*3/4;
1284
	unsigned int max_nr_writes = throtl_grp_quantum - max_nr_reads;
1285 1286 1287 1288
	struct bio *bio;

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

1289
	while ((bio = throtl_peek_queued(&sq->queued[READ])) &&
1290
	       tg_may_dispatch(tg, bio, NULL)) {
1291

1292
		tg_dispatch_one_bio(tg, bio_data_dir(bio));
1293 1294 1295 1296 1297 1298
		nr_reads++;

		if (nr_reads >= max_nr_reads)
			break;
	}

1299
	while ((bio = throtl_peek_queued(&sq->queued[WRITE])) &&
1300
	       tg_may_dispatch(tg, bio, NULL)) {
1301

1302
		tg_dispatch_one_bio(tg, bio_data_dir(bio));
1303 1304 1305 1306 1307 1308 1309 1310 1311
		nr_writes++;

		if (nr_writes >= max_nr_writes)
			break;
	}

	return nr_reads + nr_writes;
}

1312
static int throtl_select_dispatch(struct throtl_service_queue *parent_sq)
1313 1314 1315 1316
{
	unsigned int nr_disp = 0;

	while (1) {
1317
		struct throtl_grp *tg = throtl_rb_first(parent_sq);
1318
		struct throtl_service_queue *sq;
1319 1320 1321 1322 1323 1324 1325

		if (!tg)
			break;

		if (time_before(jiffies, tg->disptime))
			break;

1326
		throtl_dequeue_tg(tg);
1327

1328
		nr_disp += throtl_dispatch_tg(tg);
1329

1330
		sq = &tg->service_queue;
1331
		if (sq->nr_queued[0] || sq->nr_queued[1])
1332
			tg_update_disptime(tg);
1333 1334 1335 1336 1337 1338 1339 1340

		if (nr_disp >= throtl_quantum)
			break;
	}

	return nr_disp;
}

1341 1342
static bool throtl_can_upgrade(struct throtl_data *td,
	struct throtl_grp *this_tg);
1343 1344 1345 1346 1347 1348 1349
/**
 * throtl_pending_timer_fn - timer function for service_queue->pending_timer
 * @arg: the throtl_service_queue being serviced
 *
 * This timer is armed when a child throtl_grp with active bio's become
 * pending and queued on the service_queue's pending_tree and expires when
 * the first child throtl_grp should be dispatched.  This function
1350 1351 1352 1353 1354 1355 1356
 * dispatches bio's from the children throtl_grps to the parent
 * service_queue.
 *
 * If the parent's parent is another throtl_grp, dispatching is propagated
 * by either arming its pending_timer or repeating dispatch directly.  If
 * the top-level service_tree is reached, throtl_data->dispatch_work is
 * kicked so that the ready bio's are issued.
1357
 */
1358
static void throtl_pending_timer_fn(struct timer_list *t)
1359
{
1360
	struct throtl_service_queue *sq = from_timer(sq, t, pending_timer);
1361
	struct throtl_grp *tg = sq_to_tg(sq);
1362
	struct throtl_data *td = sq_to_td(sq);
1363
	struct request_queue *q = td->queue;
1364 1365
	struct throtl_service_queue *parent_sq;
	bool dispatched;
1366
	int ret;
1367 1368

	spin_lock_irq(q->queue_lock);
1369 1370 1371
	if (throtl_can_upgrade(td, NULL))
		throtl_upgrade_state(td);

1372 1373 1374
again:
	parent_sq = sq->parent_sq;
	dispatched = false;
1375

1376 1377
	while (true) {
		throtl_log(sq, "dispatch nr_queued=%u read=%u write=%u",
1378 1379
			   sq->nr_queued[READ] + sq->nr_queued[WRITE],
			   sq->nr_queued[READ], sq->nr_queued[WRITE]);
1380 1381 1382 1383 1384 1385

		ret = throtl_select_dispatch(sq);
		if (ret) {
			throtl_log(sq, "bios disp=%u", ret);
			dispatched = true;
		}
1386

1387 1388
		if (throtl_schedule_next_dispatch(sq, false))
			break;
1389

1390 1391 1392 1393
		/* this dispatch windows is still open, relax and repeat */
		spin_unlock_irq(q->queue_lock);
		cpu_relax();
		spin_lock_irq(q->queue_lock);
1394
	}
1395

1396 1397
	if (!dispatched)
		goto out_unlock;
1398

1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414
	if (parent_sq) {
		/* @parent_sq is another throl_grp, propagate dispatch */
		if (tg->flags & THROTL_TG_WAS_EMPTY) {
			tg_update_disptime(tg);
			if (!throtl_schedule_next_dispatch(parent_sq, false)) {
				/* window is already open, repeat dispatching */
				sq = parent_sq;
				tg = sq_to_tg(sq);
				goto again;
			}
		}
	} else {
		/* reached the top-level, queue issueing */
		queue_work(kthrotld_workqueue, &td->dispatch_work);
	}
out_unlock:
1415
	spin_unlock_irq(q->queue_lock);
1416
}
1417

1418 1419 1420 1421 1422 1423 1424 1425
/**
 * blk_throtl_dispatch_work_fn - work function for throtl_data->dispatch_work
 * @work: work item being executed
 *
 * This function is queued for execution when bio's reach the bio_lists[]
 * of throtl_data->service_queue.  Those bio's are ready and issued by this
 * function.
 */
1426
static void blk_throtl_dispatch_work_fn(struct work_struct *work)
1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439
{
	struct throtl_data *td = container_of(work, struct throtl_data,
					      dispatch_work);
	struct throtl_service_queue *td_sq = &td->service_queue;
	struct request_queue *q = td->queue;
	struct bio_list bio_list_on_stack;
	struct bio *bio;
	struct blk_plug plug;
	int rw;

	bio_list_init(&bio_list_on_stack);

	spin_lock_irq(q->queue_lock);
1440 1441 1442
	for (rw = READ; rw <= WRITE; rw++)
		while ((bio = throtl_pop_queued(&td_sq->queued[rw], NULL)))
			bio_list_add(&bio_list_on_stack, bio);
1443 1444 1445
	spin_unlock_irq(q->queue_lock);

	if (!bio_list_empty(&bio_list_on_stack)) {
1446
		blk_start_plug(&plug);
1447 1448
		while((bio = bio_list_pop(&bio_list_on_stack)))
			generic_make_request(bio);
1449
		blk_finish_plug(&plug);
1450 1451 1452
	}
}

1453 1454
static u64 tg_prfill_conf_u64(struct seq_file *sf, struct blkg_policy_data *pd,
			      int off)
1455
{
1456 1457
	struct throtl_grp *tg = pd_to_tg(pd);
	u64 v = *(u64 *)((void *)tg + off);
1458

1459
	if (v == U64_MAX)
1460
		return 0;
1461
	return __blkg_prfill_u64(sf, pd, v);
1462 1463
}

1464 1465
static u64 tg_prfill_conf_uint(struct seq_file *sf, struct blkg_policy_data *pd,
			       int off)
1466
{
1467 1468
	struct throtl_grp *tg = pd_to_tg(pd);
	unsigned int v = *(unsigned int *)((void *)tg + off);
1469

1470
	if (v == UINT_MAX)
1471
		return 0;
1472
	return __blkg_prfill_u64(sf, pd, v);
1473 1474
}

1475
static int tg_print_conf_u64(struct seq_file *sf, void *v)
1476
{
1477 1478
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_conf_u64,
			  &blkcg_policy_throtl, seq_cft(sf)->private, false);
1479
	return 0;
1480 1481
}

1482
static int tg_print_conf_uint(struct seq_file *sf, void *v)
1483
{
1484 1485
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_conf_uint,
			  &blkcg_policy_throtl, seq_cft(sf)->private, false);
1486
	return 0;
1487 1488
}

1489
static void tg_conf_updated(struct throtl_grp *tg, bool global)
1490
{
1491
	struct throtl_service_queue *sq = &tg->service_queue;
1492
	struct cgroup_subsys_state *pos_css;
1493
	struct blkcg_gq *blkg;
1494

1495 1496
	throtl_log(&tg->service_queue,
		   "limit change rbps=%llu wbps=%llu riops=%u wiops=%u",
1497 1498
		   tg_bps_limit(tg, READ), tg_bps_limit(tg, WRITE),
		   tg_iops_limit(tg, READ), tg_iops_limit(tg, WRITE));
1499

1500 1501 1502 1503 1504 1505 1506
	/*
	 * Update has_rules[] flags for the updated tg's subtree.  A tg is
	 * considered to have rules if either the tg itself or any of its
	 * ancestors has rules.  This identifies groups without any
	 * restrictions in the whole hierarchy and allows them to bypass
	 * blk-throttle.
	 */
1507 1508
	blkg_for_each_descendant_pre(blkg, pos_css,
			global ? tg->td->queue->root_blkg : tg_to_blkg(tg)) {
1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526
		struct throtl_grp *this_tg = blkg_to_tg(blkg);
		struct throtl_grp *parent_tg;

		tg_update_has_rules(this_tg);
		/* ignore root/second level */
		if (!cgroup_subsys_on_dfl(io_cgrp_subsys) || !blkg->parent ||
		    !blkg->parent->parent)
			continue;
		parent_tg = blkg_to_tg(blkg->parent);
		/*
		 * make sure all children has lower idle time threshold and
		 * higher latency target
		 */
		this_tg->idletime_threshold = min(this_tg->idletime_threshold,
				parent_tg->idletime_threshold);
		this_tg->latency_target = max(this_tg->latency_target,
				parent_tg->latency_target);
	}
1527

1528 1529 1530 1531 1532 1533 1534 1535
	/*
	 * We're already holding queue_lock and know @tg is valid.  Let's
	 * apply the new config directly.
	 *
	 * Restart the slices for both READ and WRITES. It might happen
	 * that a group's limit are dropped suddenly and we don't want to
	 * account recently dispatched IO with new low rate.
	 */
1536 1537
	throtl_start_new_slice(tg, 0);
	throtl_start_new_slice(tg, 1);
1538

1539
	if (tg->flags & THROTL_TG_PENDING) {
1540
		tg_update_disptime(tg);
1541
		throtl_schedule_next_dispatch(sq->parent_sq, true);
1542
	}
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561
}

static ssize_t tg_set_conf(struct kernfs_open_file *of,
			   char *buf, size_t nbytes, loff_t off, bool is_u64)
{
	struct blkcg *blkcg = css_to_blkcg(of_css(of));
	struct blkg_conf_ctx ctx;
	struct throtl_grp *tg;
	int ret;
	u64 v;

	ret = blkg_conf_prep(blkcg, &blkcg_policy_throtl, buf, &ctx);
	if (ret)
		return ret;

	ret = -EINVAL;
	if (sscanf(ctx.body, "%llu", &v) != 1)
		goto out_finish;
	if (!v)
1562
		v = U64_MAX;
1563 1564 1565 1566 1567 1568 1569

	tg = blkg_to_tg(ctx.blkg);

	if (is_u64)
		*(u64 *)((void *)tg + of_cft(of)->private) = v;
	else
		*(unsigned int *)((void *)tg + of_cft(of)->private) = v;
1570

1571
	tg_conf_updated(tg, false);
1572 1573
	ret = 0;
out_finish:
1574
	blkg_conf_finish(&ctx);
1575
	return ret ?: nbytes;
1576 1577
}

1578 1579
static ssize_t tg_set_conf_u64(struct kernfs_open_file *of,
			       char *buf, size_t nbytes, loff_t off)
1580
{
1581
	return tg_set_conf(of, buf, nbytes, off, true);
1582 1583
}

1584 1585
static ssize_t tg_set_conf_uint(struct kernfs_open_file *of,
				char *buf, size_t nbytes, loff_t off)
1586
{
1587
	return tg_set_conf(of, buf, nbytes, off, false);
1588 1589
}

1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
static u64 tg_prfill_rwstat_field(struct seq_file *sf,
				  struct blkg_policy_data *pd,
				  int off)
{
	struct throtl_grp *tg = pd_to_tg(pd);
	struct blkg_rwstat rwstat = blkg_rwstat_read((void *)tg + off);

	return __blkg_prfill_rwstat(sf, pd, &rwstat);
}

1600
static int tg_print_rwstat(struct seq_file *sf, void *v)
1601 1602 1603 1604 1605 1606 1607
{
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)),
			  tg_prfill_rwstat_field, &blkcg_policy_throtl,
			  seq_cft(sf)->private, true);
	return 0;
}

1608
static struct cftype throtl_legacy_files[] = {
1609 1610
	{
		.name = "throttle.read_bps_device",
1611
		.private = offsetof(struct throtl_grp, bps[READ][LIMIT_MAX]),
1612
		.seq_show = tg_print_conf_u64,
1613
		.write = tg_set_conf_u64,
1614 1615 1616
	},
	{
		.name = "throttle.write_bps_device",
1617
		.private = offsetof(struct throtl_grp, bps[WRITE][LIMIT_MAX]),
1618
		.seq_show = tg_print_conf_u64,
1619
		.write = tg_set_conf_u64,
1620 1621 1622
	},
	{
		.name = "throttle.read_iops_device",
1623
		.private = offsetof(struct throtl_grp, iops[READ][LIMIT_MAX]),
1624
		.seq_show = tg_print_conf_uint,
1625
		.write = tg_set_conf_uint,
1626 1627 1628
	},
	{
		.name = "throttle.write_iops_device",
1629
		.private = offsetof(struct throtl_grp, iops[WRITE][LIMIT_MAX]),
1630
		.seq_show = tg_print_conf_uint,
1631
		.write = tg_set_conf_uint,
1632 1633 1634
	},
	{
		.name = "throttle.io_service_bytes",
1635 1636
		.private = (unsigned long)&blkcg_policy_throtl,
		.seq_show = blkg_print_stat_bytes,
1637
	},
1638 1639 1640 1641 1642
	{
		.name = "throttle.io_service_bytes_recursive",
		.private = (unsigned long)&blkcg_policy_throtl,
		.seq_show = blkg_print_stat_bytes_recursive,
	},
1643 1644
	{
		.name = "throttle.io_serviced",
1645 1646
		.private = (unsigned long)&blkcg_policy_throtl,
		.seq_show = blkg_print_stat_ios,
1647
	},
1648 1649 1650 1651 1652
	{
		.name = "throttle.io_serviced_recursive",
		.private = (unsigned long)&blkcg_policy_throtl,
		.seq_show = blkg_print_stat_ios_recursive,
	},
1653 1654 1655
	{
		.name = "throttle.io_service_time",
		.private = offsetof(struct throtl_grp, service_time),
1656
		.seq_show = tg_print_rwstat,
1657 1658 1659 1660
	},
	{
		.name = "throttle.io_wait_time",
		.private = offsetof(struct throtl_grp, wait_time),
1661
		.seq_show = tg_print_rwstat,
1662
	},
1663 1664 1665
	{
		.name = "throttle.total_bytes_queued",
		.private = offsetof(struct throtl_grp, total_bytes_queued),
1666
		.seq_show = tg_print_rwstat,
1667 1668 1669 1670
	},
	{
		.name = "throttle.total_io_queued",
		.private = offsetof(struct throtl_grp, total_io_queued),
1671
		.seq_show = tg_print_rwstat,
1672
	},
1673 1674 1675
	{ }	/* terminate */
};

S
Shaohua Li 已提交
1676
static u64 tg_prfill_limit(struct seq_file *sf, struct blkg_policy_data *pd,
1677 1678 1679 1680 1681
			 int off)
{
	struct throtl_grp *tg = pd_to_tg(pd);
	const char *dname = blkg_dev_name(pd->blkg);
	char bufs[4][21] = { "max", "max", "max", "max" };
S
Shaohua Li 已提交
1682 1683
	u64 bps_dft;
	unsigned int iops_dft;
1684
	char idle_time[26] = "";
1685
	char latency_time[26] = "";
1686 1687 1688

	if (!dname)
		return 0;
1689

S
Shaohua Li 已提交
1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700
	if (off == LIMIT_LOW) {
		bps_dft = 0;
		iops_dft = 0;
	} else {
		bps_dft = U64_MAX;
		iops_dft = UINT_MAX;
	}

	if (tg->bps_conf[READ][off] == bps_dft &&
	    tg->bps_conf[WRITE][off] == bps_dft &&
	    tg->iops_conf[READ][off] == iops_dft &&
1701
	    tg->iops_conf[WRITE][off] == iops_dft &&
1702
	    (off != LIMIT_LOW ||
1703
	     (tg->idletime_threshold_conf == DFL_IDLE_THRESHOLD &&
1704
	      tg->latency_target_conf == DFL_LATENCY_TARGET)))
1705 1706
		return 0;

1707
	if (tg->bps_conf[READ][off] != U64_MAX)
1708
		snprintf(bufs[0], sizeof(bufs[0]), "%llu",
S
Shaohua Li 已提交
1709
			tg->bps_conf[READ][off]);
1710
	if (tg->bps_conf[WRITE][off] != U64_MAX)
1711
		snprintf(bufs[1], sizeof(bufs[1]), "%llu",
S
Shaohua Li 已提交
1712
			tg->bps_conf[WRITE][off]);
1713
	if (tg->iops_conf[READ][off] != UINT_MAX)
1714
		snprintf(bufs[2], sizeof(bufs[2]), "%u",
S
Shaohua Li 已提交
1715
			tg->iops_conf[READ][off]);
1716
	if (tg->iops_conf[WRITE][off] != UINT_MAX)
1717
		snprintf(bufs[3], sizeof(bufs[3]), "%u",
S
Shaohua Li 已提交
1718
			tg->iops_conf[WRITE][off]);
1719
	if (off == LIMIT_LOW) {
1720
		if (tg->idletime_threshold_conf == ULONG_MAX)
1721 1722 1723
			strcpy(idle_time, " idle=max");
		else
			snprintf(idle_time, sizeof(idle_time), " idle=%lu",
1724
				tg->idletime_threshold_conf);
1725

1726
		if (tg->latency_target_conf == ULONG_MAX)
1727 1728 1729
			strcpy(latency_time, " latency=max");
		else
			snprintf(latency_time, sizeof(latency_time),
1730
				" latency=%lu", tg->latency_target_conf);
1731
	}
1732

1733 1734 1735
	seq_printf(sf, "%s rbps=%s wbps=%s riops=%s wiops=%s%s%s\n",
		   dname, bufs[0], bufs[1], bufs[2], bufs[3], idle_time,
		   latency_time);
1736 1737 1738
	return 0;
}

S
Shaohua Li 已提交
1739
static int tg_print_limit(struct seq_file *sf, void *v)
1740
{
S
Shaohua Li 已提交
1741
	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_limit,
1742 1743 1744 1745
			  &blkcg_policy_throtl, seq_cft(sf)->private, false);
	return 0;
}

S
Shaohua Li 已提交
1746
static ssize_t tg_set_limit(struct kernfs_open_file *of,
1747 1748 1749 1750 1751 1752
			  char *buf, size_t nbytes, loff_t off)
{
	struct blkcg *blkcg = css_to_blkcg(of_css(of));
	struct blkg_conf_ctx ctx;
	struct throtl_grp *tg;
	u64 v[4];
1753
	unsigned long idle_time;
1754
	unsigned long latency_time;
1755
	int ret;
S
Shaohua Li 已提交
1756
	int index = of_cft(of)->private;
1757 1758 1759 1760 1761 1762 1763

	ret = blkg_conf_prep(blkcg, &blkcg_policy_throtl, buf, &ctx);
	if (ret)
		return ret;

	tg = blkg_to_tg(ctx.blkg);

S
Shaohua Li 已提交
1764 1765 1766 1767
	v[0] = tg->bps_conf[READ][index];
	v[1] = tg->bps_conf[WRITE][index];
	v[2] = tg->iops_conf[READ][index];
	v[3] = tg->iops_conf[WRITE][index];
1768

1769 1770
	idle_time = tg->idletime_threshold_conf;
	latency_time = tg->latency_target_conf;
1771 1772 1773
	while (true) {
		char tok[27];	/* wiops=18446744073709551616 */
		char *p;
1774
		u64 val = U64_MAX;
1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801
		int len;

		if (sscanf(ctx.body, "%26s%n", tok, &len) != 1)
			break;
		if (tok[0] == '\0')
			break;
		ctx.body += len;

		ret = -EINVAL;
		p = tok;
		strsep(&p, "=");
		if (!p || (sscanf(p, "%llu", &val) != 1 && strcmp(p, "max")))
			goto out_finish;

		ret = -ERANGE;
		if (!val)
			goto out_finish;

		ret = -EINVAL;
		if (!strcmp(tok, "rbps"))
			v[0] = val;
		else if (!strcmp(tok, "wbps"))
			v[1] = val;
		else if (!strcmp(tok, "riops"))
			v[2] = min_t(u64, val, UINT_MAX);
		else if (!strcmp(tok, "wiops"))
			v[3] = min_t(u64, val, UINT_MAX);
1802 1803
		else if (off == LIMIT_LOW && !strcmp(tok, "idle"))
			idle_time = val;
1804 1805
		else if (off == LIMIT_LOW && !strcmp(tok, "latency"))
			latency_time = val;
1806 1807 1808 1809
		else
			goto out_finish;
	}

S
Shaohua Li 已提交
1810 1811 1812 1813
	tg->bps_conf[READ][index] = v[0];
	tg->bps_conf[WRITE][index] = v[1];
	tg->iops_conf[READ][index] = v[2];
	tg->iops_conf[WRITE][index] = v[3];
1814

S
Shaohua Li 已提交
1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828
	if (index == LIMIT_MAX) {
		tg->bps[READ][index] = v[0];
		tg->bps[WRITE][index] = v[1];
		tg->iops[READ][index] = v[2];
		tg->iops[WRITE][index] = v[3];
	}
	tg->bps[READ][LIMIT_LOW] = min(tg->bps_conf[READ][LIMIT_LOW],
		tg->bps_conf[READ][LIMIT_MAX]);
	tg->bps[WRITE][LIMIT_LOW] = min(tg->bps_conf[WRITE][LIMIT_LOW],
		tg->bps_conf[WRITE][LIMIT_MAX]);
	tg->iops[READ][LIMIT_LOW] = min(tg->iops_conf[READ][LIMIT_LOW],
		tg->iops_conf[READ][LIMIT_MAX]);
	tg->iops[WRITE][LIMIT_LOW] = min(tg->iops_conf[WRITE][LIMIT_LOW],
		tg->iops_conf[WRITE][LIMIT_MAX]);
1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843
	tg->idletime_threshold_conf = idle_time;
	tg->latency_target_conf = latency_time;

	/* force user to configure all settings for low limit  */
	if (!(tg->bps[READ][LIMIT_LOW] || tg->iops[READ][LIMIT_LOW] ||
	      tg->bps[WRITE][LIMIT_LOW] || tg->iops[WRITE][LIMIT_LOW]) ||
	    tg->idletime_threshold_conf == DFL_IDLE_THRESHOLD ||
	    tg->latency_target_conf == DFL_LATENCY_TARGET) {
		tg->bps[READ][LIMIT_LOW] = 0;
		tg->bps[WRITE][LIMIT_LOW] = 0;
		tg->iops[READ][LIMIT_LOW] = 0;
		tg->iops[WRITE][LIMIT_LOW] = 0;
		tg->idletime_threshold = DFL_IDLE_THRESHOLD;
		tg->latency_target = DFL_LATENCY_TARGET;
	} else if (index == LIMIT_LOW) {
1844 1845
		tg->idletime_threshold = tg->idletime_threshold_conf;
		tg->latency_target = tg->latency_target_conf;
S
Shaohua Li 已提交
1846
	}
1847 1848 1849 1850 1851 1852 1853

	blk_throtl_update_limit_valid(tg->td);
	if (tg->td->limit_valid[LIMIT_LOW]) {
		if (index == LIMIT_LOW)
			tg->td->limit_index = LIMIT_LOW;
	} else
		tg->td->limit_index = LIMIT_MAX;
1854 1855
	tg_conf_updated(tg, index == LIMIT_LOW &&
		tg->td->limit_valid[LIMIT_LOW]);
1856 1857 1858 1859 1860 1861 1862
	ret = 0;
out_finish:
	blkg_conf_finish(&ctx);
	return ret ?: nbytes;
}

static struct cftype throtl_files[] = {
S
Shaohua Li 已提交
1863 1864 1865 1866 1867 1868 1869 1870 1871
#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
	{
		.name = "low",
		.flags = CFTYPE_NOT_ON_ROOT,
		.seq_show = tg_print_limit,
		.write = tg_set_limit,
		.private = LIMIT_LOW,
	},
#endif
1872 1873 1874
	{
		.name = "max",
		.flags = CFTYPE_NOT_ON_ROOT,
S
Shaohua Li 已提交
1875 1876 1877
		.seq_show = tg_print_limit,
		.write = tg_set_limit,
		.private = LIMIT_MAX,
1878 1879 1880 1881
	},
	{ }	/* terminate */
};

1882
static void throtl_shutdown_wq(struct request_queue *q)
1883 1884 1885
{
	struct throtl_data *td = q->td;

1886
	cancel_work_sync(&td->dispatch_work);
1887 1888
}

T
Tejun Heo 已提交
1889
static struct blkcg_policy blkcg_policy_throtl = {
1890
	.dfl_cftypes		= throtl_files,
1891
	.legacy_cftypes		= throtl_legacy_files,
1892

1893
	.pd_alloc_fn		= throtl_pd_alloc,
1894
	.pd_init_fn		= throtl_pd_init,
1895
	.pd_online_fn		= throtl_pd_online,
S
Shaohua Li 已提交
1896
	.pd_offline_fn		= throtl_pd_offline,
1897
	.pd_free_fn		= throtl_pd_free,
1898
	.pd_reset_stats_fn	= throtl_pd_reset,
1899 1900
};

S
Shaohua Li 已提交
1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939
static unsigned long __tg_last_low_overflow_time(struct throtl_grp *tg)
{
	unsigned long rtime = jiffies, wtime = jiffies;

	if (tg->bps[READ][LIMIT_LOW] || tg->iops[READ][LIMIT_LOW])
		rtime = tg->last_low_overflow_time[READ];
	if (tg->bps[WRITE][LIMIT_LOW] || tg->iops[WRITE][LIMIT_LOW])
		wtime = tg->last_low_overflow_time[WRITE];
	return min(rtime, wtime);
}

/* tg should not be an intermediate node */
static unsigned long tg_last_low_overflow_time(struct throtl_grp *tg)
{
	struct throtl_service_queue *parent_sq;
	struct throtl_grp *parent = tg;
	unsigned long ret = __tg_last_low_overflow_time(tg);

	while (true) {
		parent_sq = parent->service_queue.parent_sq;
		parent = sq_to_tg(parent_sq);
		if (!parent)
			break;

		/*
		 * The parent doesn't have low limit, it always reaches low
		 * limit. Its overflow time is useless for children
		 */
		if (!parent->bps[READ][LIMIT_LOW] &&
		    !parent->iops[READ][LIMIT_LOW] &&
		    !parent->bps[WRITE][LIMIT_LOW] &&
		    !parent->iops[WRITE][LIMIT_LOW])
			continue;
		if (time_after(__tg_last_low_overflow_time(parent), ret))
			ret = __tg_last_low_overflow_time(parent);
	}
	return ret;
}

1940 1941 1942 1943 1944
static bool throtl_tg_is_idle(struct throtl_grp *tg)
{
	/*
	 * cgroup is idle if:
	 * - single idle is too long, longer than a fixed value (in case user
1945
	 *   configure a too big threshold) or 4 times of idletime threshold
1946
	 * - average think time is more than threshold
1947
	 * - IO latency is largely below threshold
1948
	 */
1949
	unsigned long time;
1950
	bool ret;
1951

1952 1953 1954 1955 1956 1957
	time = min_t(unsigned long, MAX_IDLE_TIME, 4 * tg->idletime_threshold);
	ret = tg->latency_target == DFL_LATENCY_TARGET ||
	      tg->idletime_threshold == DFL_IDLE_THRESHOLD ||
	      (ktime_get_ns() >> 10) - tg->last_finish_time > time ||
	      tg->avg_idletime > tg->idletime_threshold ||
	      (tg->latency_target && tg->bio_cnt &&
1958
		tg->bad_bio_cnt * 5 < tg->bio_cnt);
1959 1960 1961 1962 1963
	throtl_log(&tg->service_queue,
		"avg_idle=%ld, idle_threshold=%ld, bad_bio=%d, total_bio=%d, is_idle=%d, scale=%d",
		tg->avg_idletime, tg->idletime_threshold, tg->bad_bio_cnt,
		tg->bio_cnt, ret, tg->td->scale);
	return ret;
1964 1965
}

1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984
static bool throtl_tg_can_upgrade(struct throtl_grp *tg)
{
	struct throtl_service_queue *sq = &tg->service_queue;
	bool read_limit, write_limit;

	/*
	 * if cgroup reaches low limit (if low limit is 0, the cgroup always
	 * reaches), it's ok to upgrade to next limit
	 */
	read_limit = tg->bps[READ][LIMIT_LOW] || tg->iops[READ][LIMIT_LOW];
	write_limit = tg->bps[WRITE][LIMIT_LOW] || tg->iops[WRITE][LIMIT_LOW];
	if (!read_limit && !write_limit)
		return true;
	if (read_limit && sq->nr_queued[READ] &&
	    (!write_limit || sq->nr_queued[WRITE]))
		return true;
	if (write_limit && sq->nr_queued[WRITE] &&
	    (!read_limit || sq->nr_queued[READ]))
		return true;
1985 1986

	if (time_after_eq(jiffies,
1987 1988
		tg_last_low_overflow_time(tg) + tg->td->throtl_slice) &&
	    throtl_tg_is_idle(tg))
1989
		return true;
1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013
	return false;
}

static bool throtl_hierarchy_can_upgrade(struct throtl_grp *tg)
{
	while (true) {
		if (throtl_tg_can_upgrade(tg))
			return true;
		tg = sq_to_tg(tg->service_queue.parent_sq);
		if (!tg || !tg_to_blkg(tg)->parent)
			return false;
	}
	return false;
}

static bool throtl_can_upgrade(struct throtl_data *td,
	struct throtl_grp *this_tg)
{
	struct cgroup_subsys_state *pos_css;
	struct blkcg_gq *blkg;

	if (td->limit_index != LIMIT_LOW)
		return false;

2014
	if (time_before(jiffies, td->low_downgrade_time + td->throtl_slice))
S
Shaohua Li 已提交
2015 2016
		return false;

2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033
	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 == this_tg)
			continue;
		if (!list_empty(&tg_to_blkg(tg)->blkcg->css.children))
			continue;
		if (!throtl_hierarchy_can_upgrade(tg)) {
			rcu_read_unlock();
			return false;
		}
	}
	rcu_read_unlock();
	return true;
}

2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053
static void throtl_upgrade_check(struct throtl_grp *tg)
{
	unsigned long now = jiffies;

	if (tg->td->limit_index != LIMIT_LOW)
		return;

	if (time_after(tg->last_check_time + tg->td->throtl_slice, now))
		return;

	tg->last_check_time = now;

	if (!time_after_eq(now,
	     __tg_last_low_overflow_time(tg) + tg->td->throtl_slice))
		return;

	if (throtl_can_upgrade(tg->td, NULL))
		throtl_upgrade_state(tg->td);
}

2054 2055 2056 2057 2058
static void throtl_upgrade_state(struct throtl_data *td)
{
	struct cgroup_subsys_state *pos_css;
	struct blkcg_gq *blkg;

2059
	throtl_log(&td->service_queue, "upgrade to max");
2060
	td->limit_index = LIMIT_MAX;
S
Shaohua Li 已提交
2061
	td->low_upgrade_time = jiffies;
2062
	td->scale = 0;
2063 2064 2065 2066 2067 2068 2069
	rcu_read_lock();
	blkg_for_each_descendant_post(blkg, pos_css, td->queue->root_blkg) {
		struct throtl_grp *tg = blkg_to_tg(blkg);
		struct throtl_service_queue *sq = &tg->service_queue;

		tg->disptime = jiffies - 1;
		throtl_select_dispatch(sq);
2070
		throtl_schedule_next_dispatch(sq, true);
2071 2072 2073
	}
	rcu_read_unlock();
	throtl_select_dispatch(&td->service_queue);
2074
	throtl_schedule_next_dispatch(&td->service_queue, true);
2075 2076 2077
	queue_work(kthrotld_workqueue, &td->dispatch_work);
}

S
Shaohua Li 已提交
2078 2079
static void throtl_downgrade_state(struct throtl_data *td, int new)
{
2080 2081
	td->scale /= 2;

2082
	throtl_log(&td->service_queue, "downgrade, scale %d", td->scale);
2083 2084 2085 2086 2087
	if (td->scale) {
		td->low_upgrade_time = jiffies - td->scale * td->throtl_slice;
		return;
	}

S
Shaohua Li 已提交
2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100
	td->limit_index = new;
	td->low_downgrade_time = jiffies;
}

static bool throtl_tg_can_downgrade(struct throtl_grp *tg)
{
	struct throtl_data *td = tg->td;
	unsigned long now = jiffies;

	/*
	 * If cgroup is below low limit, consider downgrade and throttle other
	 * cgroups
	 */
2101 2102
	if (time_after_eq(now, td->low_upgrade_time + td->throtl_slice) &&
	    time_after_eq(now, tg_last_low_overflow_time(tg) +
2103 2104 2105
					td->throtl_slice) &&
	    (!throtl_tg_is_idle(tg) ||
	     !list_empty(&tg_to_blkg(tg)->blkcg->css.children)))
S
Shaohua Li 已提交
2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133
		return true;
	return false;
}

static bool throtl_hierarchy_can_downgrade(struct throtl_grp *tg)
{
	while (true) {
		if (!throtl_tg_can_downgrade(tg))
			return false;
		tg = sq_to_tg(tg->service_queue.parent_sq);
		if (!tg || !tg_to_blkg(tg)->parent)
			break;
	}
	return true;
}

static void throtl_downgrade_check(struct throtl_grp *tg)
{
	uint64_t bps;
	unsigned int iops;
	unsigned long elapsed_time;
	unsigned long now = jiffies;

	if (tg->td->limit_index != LIMIT_MAX ||
	    !tg->td->limit_valid[LIMIT_LOW])
		return;
	if (!list_empty(&tg_to_blkg(tg)->blkcg->css.children))
		return;
2134
	if (time_after(tg->last_check_time + tg->td->throtl_slice, now))
S
Shaohua Li 已提交
2135 2136 2137 2138 2139
		return;

	elapsed_time = now - tg->last_check_time;
	tg->last_check_time = now;

2140 2141
	if (time_before(now, tg_last_low_overflow_time(tg) +
			tg->td->throtl_slice))
S
Shaohua Li 已提交
2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182
		return;

	if (tg->bps[READ][LIMIT_LOW]) {
		bps = tg->last_bytes_disp[READ] * HZ;
		do_div(bps, elapsed_time);
		if (bps >= tg->bps[READ][LIMIT_LOW])
			tg->last_low_overflow_time[READ] = now;
	}

	if (tg->bps[WRITE][LIMIT_LOW]) {
		bps = tg->last_bytes_disp[WRITE] * HZ;
		do_div(bps, elapsed_time);
		if (bps >= tg->bps[WRITE][LIMIT_LOW])
			tg->last_low_overflow_time[WRITE] = now;
	}

	if (tg->iops[READ][LIMIT_LOW]) {
		iops = tg->last_io_disp[READ] * HZ / elapsed_time;
		if (iops >= tg->iops[READ][LIMIT_LOW])
			tg->last_low_overflow_time[READ] = now;
	}

	if (tg->iops[WRITE][LIMIT_LOW]) {
		iops = tg->last_io_disp[WRITE] * HZ / elapsed_time;
		if (iops >= tg->iops[WRITE][LIMIT_LOW])
			tg->last_low_overflow_time[WRITE] = now;
	}

	/*
	 * If cgroup is below low limit, consider downgrade and throttle other
	 * cgroups
	 */
	if (throtl_hierarchy_can_downgrade(tg))
		throtl_downgrade_state(tg->td, LIMIT_LOW);

	tg->last_bytes_disp[READ] = 0;
	tg->last_bytes_disp[WRITE] = 0;
	tg->last_io_disp[READ] = 0;
	tg->last_io_disp[WRITE] = 0;
}

2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195
static void blk_throtl_update_idletime(struct throtl_grp *tg)
{
	unsigned long now = ktime_get_ns() >> 10;
	unsigned long last_finish_time = tg->last_finish_time;

	if (now <= last_finish_time || last_finish_time == 0 ||
	    last_finish_time == tg->checked_last_finish_time)
		return;

	tg->avg_idletime = (tg->avg_idletime * 7 + now - last_finish_time) >> 3;
	tg->checked_last_finish_time = last_finish_time;
}

2196 2197 2198
#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
static void throtl_update_latency_buckets(struct throtl_data *td)
{
2199 2200 2201 2202
	struct avg_latency_bucket avg_latency[2][LATENCY_BUCKET_SIZE];
	int i, cpu, rw;
	unsigned long last_latency[2] = { 0 };
	unsigned long latency[2];
2203 2204 2205 2206 2207 2208 2209 2210

	if (!blk_queue_nonrot(td->queue))
		return;
	if (time_before(jiffies, td->last_calculate_time + HZ))
		return;
	td->last_calculate_time = jiffies;

	memset(avg_latency, 0, sizeof(avg_latency));
2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225
	for (rw = READ; rw <= WRITE; rw++) {
		for (i = 0; i < LATENCY_BUCKET_SIZE; i++) {
			struct latency_bucket *tmp = &td->tmp_buckets[rw][i];

			for_each_possible_cpu(cpu) {
				struct latency_bucket *bucket;

				/* this isn't race free, but ok in practice */
				bucket = per_cpu_ptr(td->latency_buckets[rw],
					cpu);
				tmp->total_latency += bucket[i].total_latency;
				tmp->samples += bucket[i].samples;
				bucket[i].total_latency = 0;
				bucket[i].samples = 0;
			}
2226

2227 2228
			if (tmp->samples >= 32) {
				int samples = tmp->samples;
2229

2230
				latency[rw] = tmp->total_latency;
2231

2232 2233 2234 2235 2236 2237 2238
				tmp->total_latency = 0;
				tmp->samples = 0;
				latency[rw] /= samples;
				if (latency[rw] == 0)
					continue;
				avg_latency[rw][i].latency = latency[rw];
			}
2239 2240 2241
		}
	}

2242 2243 2244 2245 2246 2247 2248 2249
	for (rw = READ; rw <= WRITE; rw++) {
		for (i = 0; i < LATENCY_BUCKET_SIZE; i++) {
			if (!avg_latency[rw][i].latency) {
				if (td->avg_buckets[rw][i].latency < last_latency[rw])
					td->avg_buckets[rw][i].latency =
						last_latency[rw];
				continue;
			}
2250

2251 2252 2253 2254 2255
			if (!td->avg_buckets[rw][i].valid)
				latency[rw] = avg_latency[rw][i].latency;
			else
				latency[rw] = (td->avg_buckets[rw][i].latency * 7 +
					avg_latency[rw][i].latency) >> 3;
2256

2257 2258 2259 2260 2261
			td->avg_buckets[rw][i].latency = max(latency[rw],
				last_latency[rw]);
			td->avg_buckets[rw][i].valid = true;
			last_latency[rw] = td->avg_buckets[rw][i].latency;
		}
2262
	}
2263 2264 2265

	for (i = 0; i < LATENCY_BUCKET_SIZE; i++)
		throtl_log(&td->service_queue,
2266 2267 2268 2269 2270 2271
			"Latency bucket %d: read latency=%ld, read valid=%d, "
			"write latency=%ld, write valid=%d", i,
			td->avg_buckets[READ][i].latency,
			td->avg_buckets[READ][i].valid,
			td->avg_buckets[WRITE][i].latency,
			td->avg_buckets[WRITE][i].valid);
2272 2273 2274 2275 2276 2277 2278
}
#else
static inline void throtl_update_latency_buckets(struct throtl_data *td)
{
}
#endif

2279 2280 2281
static void blk_throtl_assoc_bio(struct throtl_grp *tg, struct bio *bio)
{
#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
2282 2283 2284
	/* fallback to root_blkg if we fail to get a blkg ref */
	if (bio->bi_css && (bio_associate_blkg(bio, tg_to_blkg(tg)) == -ENODEV))
		bio_associate_blkg(bio, bio->bi_disk->queue->root_blkg);
2285
	bio_issue_init(&bio->bi_issue, bio_sectors(bio));
2286 2287 2288
#endif
}

2289 2290
bool blk_throtl_bio(struct request_queue *q, struct blkcg_gq *blkg,
		    struct bio *bio)
2291
{
2292
	struct throtl_qnode *qn = NULL;
2293
	struct throtl_grp *tg = blkg_to_tg(blkg ?: q->root_blkg);
2294
	struct throtl_service_queue *sq;
2295
	bool rw = bio_data_dir(bio);
2296
	bool throttled = false;
2297
	struct throtl_data *td = tg->td;
2298

2299 2300
	WARN_ON_ONCE(!rcu_read_lock_held());

2301
	/* see throtl_charge_bio() */
2302 2303 2304 2305 2306 2307
	if (bio_flagged(bio, BIO_THROTTLED))
		goto out;

	throtl_bio_stats_start(bio, tg);

	if (!tg->has_rules[rw])
2308
		goto out;
2309 2310

	spin_lock_irq(q->queue_lock);
2311

2312 2313
	throtl_update_latency_buckets(td);

2314
	if (unlikely(blk_queue_bypass(q)))
2315
		goto out_unlock;
2316

2317
	blk_throtl_assoc_bio(tg, bio);
2318 2319
	blk_throtl_update_idletime(tg);

2320 2321
	sq = &tg->service_queue;

2322
again:
2323
	while (true) {
S
Shaohua Li 已提交
2324 2325 2326
		if (tg->last_low_overflow_time[rw] == 0)
			tg->last_low_overflow_time[rw] = jiffies;
		throtl_downgrade_check(tg);
2327
		throtl_upgrade_check(tg);
2328 2329 2330
		/* throtl is FIFO - if bios are already queued, should queue */
		if (sq->nr_queued[rw])
			break;
2331

2332
		/* if above limits, break to queue */
2333
		if (!tg_may_dispatch(tg, bio, NULL)) {
S
Shaohua Li 已提交
2334
			tg->last_low_overflow_time[rw] = jiffies;
2335 2336
			if (throtl_can_upgrade(td, tg)) {
				throtl_upgrade_state(td);
2337 2338
				goto again;
			}
2339
			break;
2340
		}
2341 2342

		/* within limits, let's charge and dispatch directly */
2343
		throtl_charge_bio(tg, bio);
2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355

		/*
		 * We need to trim slice even when bios are not being queued
		 * otherwise it might happen that a bio is not queued for
		 * a long time and slice keeps on extending and trim is not
		 * called for a long time. Now if limits are reduced suddenly
		 * we take into account all the IO dispatched so far at new
		 * low rate and * newly queued IO gets a really long dispatch
		 * time.
		 *
		 * So keep on trimming slice even if bio is not queued.
		 */
2356
		throtl_trim_slice(tg, rw);
2357 2358 2359 2360 2361 2362

		/*
		 * @bio passed through this layer without being throttled.
		 * Climb up the ladder.  If we''re already at the top, it
		 * can be executed directly.
		 */
2363
		qn = &tg->qnode_on_parent[rw];
2364 2365 2366 2367
		sq = sq->parent_sq;
		tg = sq_to_tg(sq);
		if (!tg)
			goto out_unlock;
2368 2369
	}

2370
	/* out-of-limit, queue to @tg */
2371 2372
	throtl_log(sq, "[%c] bio. bdisp=%llu sz=%u bps=%llu iodisp=%u iops=%u queued=%d/%d",
		   rw == READ ? 'R' : 'W',
2373 2374 2375
		   tg->bytes_disp[rw], bio->bi_iter.bi_size,
		   tg_bps_limit(tg, rw),
		   tg->io_disp[rw], tg_iops_limit(tg, rw),
2376
		   sq->nr_queued[READ], sq->nr_queued[WRITE]);
2377

S
Shaohua Li 已提交
2378 2379
	tg->last_low_overflow_time[rw] = jiffies;

2380
	td->nr_queued[rw]++;
2381
	throtl_add_bio_tg(bio, qn, tg);
2382
	throttled = true;
2383

2384 2385 2386 2387 2388 2389
	/*
	 * Update @tg's dispatch time and force schedule dispatch if @tg
	 * was empty before @bio.  The forced scheduling isn't likely to
	 * cause undue delay as @bio is likely to be dispatched directly if
	 * its @tg's disptime is not in the future.
	 */
2390
	if (tg->flags & THROTL_TG_WAS_EMPTY) {
2391
		tg_update_disptime(tg);
2392
		throtl_schedule_next_dispatch(tg->service_queue.parent_sq, true);
2393 2394
	}

2395
out_unlock:
2396
	spin_unlock_irq(q->queue_lock);
2397
out:
2398 2399
	if (!throttled)
		bio_set_io_start_time_ns(bio);
S
Shaohua Li 已提交
2400
	bio_set_flag(bio, BIO_THROTTLED);
2401 2402 2403

#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
	if (throttled || !td->track_bio_latency)
2404
		bio->bi_issue.value |= BIO_ISSUE_THROTL_SKIP_LATENCY;
2405
#endif
2406
	return throttled;
2407 2408
}

2409
#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
2410 2411 2412 2413 2414 2415
static void throtl_track_latency(struct throtl_data *td, sector_t size,
	int op, unsigned long time)
{
	struct latency_bucket *latency;
	int index;

2416 2417
	if (!td || td->limit_index != LIMIT_LOW ||
	    !(op == REQ_OP_READ || op == REQ_OP_WRITE) ||
2418 2419 2420 2421 2422
	    !blk_queue_nonrot(td->queue))
		return;

	index = request_bucket_index(size);

2423
	latency = get_cpu_ptr(td->latency_buckets[op]);
2424 2425
	latency[index].total_latency += time;
	latency[index].samples++;
2426
	put_cpu_ptr(td->latency_buckets[op]);
2427 2428 2429 2430 2431 2432 2433
}

void blk_throtl_stat_add(struct request *rq, u64 time_ns)
{
	struct request_queue *q = rq->q;
	struct throtl_data *td = q->td;

2434
	throtl_track_latency(td, rq->throtl_size, req_op(rq), time_ns >> 10);
2435 2436
}

2437 2438
void blk_throtl_bio_endio(struct bio *bio)
{
2439
	struct blkcg_gq *blkg;
2440
	struct throtl_grp *tg;
2441 2442 2443 2444
	u64 finish_time_ns;
	unsigned long finish_time;
	unsigned long start_time;
	unsigned long lat;
2445
	int rw = bio_data_dir(bio);
2446

2447 2448
	blkg = bio->bi_blkg;
	if (!blkg)
2449
		return;
2450
	tg = blkg_to_tg(blkg);
2451

2452 2453 2454
	finish_time_ns = ktime_get_ns();
	tg->last_finish_time = finish_time_ns >> 10;

2455 2456
	start_time = bio_issue_time(&bio->bi_issue) >> 10;
	finish_time = __bio_issue_time(finish_time_ns) >> 10;
2457
	if (!start_time || finish_time <= start_time)
2458 2459 2460
		return;

	lat = finish_time - start_time;
2461
	/* this is only for bio based driver */
2462 2463 2464
	if (!(bio->bi_issue.value & BIO_ISSUE_THROTL_SKIP_LATENCY))
		throtl_track_latency(tg->td, bio_issue_size(&bio->bi_issue),
				     bio_op(bio), lat);
2465

2466
	if (tg->latency_target && lat >= tg->td->filtered_latency) {
2467 2468 2469
		int bucket;
		unsigned int threshold;

2470
		bucket = request_bucket_index(bio_issue_size(&bio->bi_issue));
2471
		threshold = tg->td->avg_buckets[rw][bucket].latency +
2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485
			tg->latency_target;
		if (lat > threshold)
			tg->bad_bio_cnt++;
		/*
		 * Not race free, could get wrong count, which means cgroups
		 * will be throttled
		 */
		tg->bio_cnt++;
	}

	if (time_after(jiffies, tg->bio_cnt_reset_time) || tg->bio_cnt > 1024) {
		tg->bio_cnt_reset_time = tg->td->throtl_slice + jiffies;
		tg->bio_cnt /= 2;
		tg->bad_bio_cnt /= 2;
2486
	}
2487 2488 2489
}
#endif

2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504
/*
 * Dispatch all bios from all children tg's queued on @parent_sq.  On
 * return, @parent_sq is guaranteed to not have any active children tg's
 * and all bios from previously active tg's are on @parent_sq->bio_lists[].
 */
static void tg_drain_bios(struct throtl_service_queue *parent_sq)
{
	struct throtl_grp *tg;

	while ((tg = throtl_rb_first(parent_sq))) {
		struct throtl_service_queue *sq = &tg->service_queue;
		struct bio *bio;

		throtl_dequeue_tg(tg);

2505
		while ((bio = throtl_peek_queued(&sq->queued[READ])))
2506
			tg_dispatch_one_bio(tg, bio_data_dir(bio));
2507
		while ((bio = throtl_peek_queued(&sq->queued[WRITE])))
2508 2509 2510 2511
			tg_dispatch_one_bio(tg, bio_data_dir(bio));
	}
}

2512 2513 2514 2515 2516 2517 2518 2519 2520 2521
/**
 * blk_throtl_drain - drain throttled bios
 * @q: request_queue to drain throttled bios for
 *
 * Dispatch all currently throttled bios on @q through ->make_request_fn().
 */
void blk_throtl_drain(struct request_queue *q)
	__releases(q->queue_lock) __acquires(q->queue_lock)
{
	struct throtl_data *td = q->td;
2522
	struct blkcg_gq *blkg;
2523
	struct cgroup_subsys_state *pos_css;
2524
	struct bio *bio;
2525
	int rw;
2526

2527
	queue_lockdep_assert_held(q);
2528
	rcu_read_lock();
2529

2530 2531 2532 2533 2534 2535
	/*
	 * Drain each tg while doing post-order walk on the blkg tree, so
	 * that all bios are propagated to td->service_queue.  It'd be
	 * better to walk service_queue tree directly but blkg walk is
	 * easier.
	 */
2536
	blkg_for_each_descendant_post(blkg, pos_css, td->queue->root_blkg)
2537
		tg_drain_bios(&blkg_to_tg(blkg)->service_queue);
2538

2539 2540 2541 2542
	/* finally, transfer bios from top-level tg's into the td */
	tg_drain_bios(&td->service_queue);

	rcu_read_unlock();
2543 2544
	spin_unlock_irq(q->queue_lock);

2545
	/* all bios now should be in td->service_queue, issue them */
2546
	for (rw = READ; rw <= WRITE; rw++)
2547 2548
		while ((bio = throtl_pop_queued(&td->service_queue.queued[rw],
						NULL)))
2549
			generic_make_request(bio);
2550 2551 2552 2553

	spin_lock_irq(q->queue_lock);
}

2554 2555 2556
int blk_throtl_init(struct request_queue *q)
{
	struct throtl_data *td;
2557
	int ret;
2558 2559 2560 2561

	td = kzalloc_node(sizeof(*td), GFP_KERNEL, q->node);
	if (!td)
		return -ENOMEM;
2562
	td->latency_buckets[READ] = __alloc_percpu(sizeof(struct latency_bucket) *
2563
		LATENCY_BUCKET_SIZE, __alignof__(u64));
2564 2565 2566 2567 2568
	if (!td->latency_buckets[READ]) {
		kfree(td);
		return -ENOMEM;
	}
	td->latency_buckets[WRITE] = __alloc_percpu(sizeof(struct latency_bucket) *
2569
		LATENCY_BUCKET_SIZE, __alignof__(u64));
2570 2571
	if (!td->latency_buckets[WRITE]) {
		free_percpu(td->latency_buckets[READ]);
2572 2573 2574
		kfree(td);
		return -ENOMEM;
	}
2575

2576
	INIT_WORK(&td->dispatch_work, blk_throtl_dispatch_work_fn);
2577
	throtl_service_queue_init(&td->service_queue);
2578

2579
	q->td = td;
2580
	td->queue = q;
V
Vivek Goyal 已提交
2581

2582
	td->limit_valid[LIMIT_MAX] = true;
S
Shaohua Li 已提交
2583
	td->limit_index = LIMIT_MAX;
S
Shaohua Li 已提交
2584 2585
	td->low_upgrade_time = jiffies;
	td->low_downgrade_time = jiffies;
2586

2587
	/* activate policy */
T
Tejun Heo 已提交
2588
	ret = blkcg_activate_policy(q, &blkcg_policy_throtl);
2589
	if (ret) {
2590 2591
		free_percpu(td->latency_buckets[READ]);
		free_percpu(td->latency_buckets[WRITE]);
2592
		kfree(td);
2593
	}
2594
	return ret;
2595 2596 2597 2598
}

void blk_throtl_exit(struct request_queue *q)
{
T
Tejun Heo 已提交
2599
	BUG_ON(!q->td);
2600
	throtl_shutdown_wq(q);
T
Tejun Heo 已提交
2601
	blkcg_deactivate_policy(q, &blkcg_policy_throtl);
2602 2603
	free_percpu(q->td->latency_buckets[READ]);
	free_percpu(q->td->latency_buckets[WRITE]);
2604
	kfree(q->td);
2605 2606
}

2607 2608 2609
void blk_throtl_register_queue(struct request_queue *q)
{
	struct throtl_data *td;
2610
	int i;
2611 2612 2613 2614

	td = q->td;
	BUG_ON(!td);

2615
	if (blk_queue_nonrot(q)) {
2616
		td->throtl_slice = DFL_THROTL_SLICE_SSD;
2617 2618
		td->filtered_latency = LATENCY_FILTERED_SSD;
	} else {
2619
		td->throtl_slice = DFL_THROTL_SLICE_HD;
2620
		td->filtered_latency = LATENCY_FILTERED_HD;
2621 2622 2623 2624
		for (i = 0; i < LATENCY_BUCKET_SIZE; i++) {
			td->avg_buckets[READ][i].latency = DFL_HD_BASELINE_LATENCY;
			td->avg_buckets[WRITE][i].latency = DFL_HD_BASELINE_LATENCY;
		}
2625
	}
2626 2627 2628 2629
#ifndef CONFIG_BLK_DEV_THROTTLING_LOW
	/* if no low limit, use previous default */
	td->throtl_slice = DFL_THROTL_SLICE_HD;
#endif
2630

2631
	td->track_bio_latency = !queue_is_rq_based(q);
2632 2633
	if (!td->track_bio_latency)
		blk_stat_enable_accounting(q);
2634 2635
}

2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661
#ifdef CONFIG_BLK_DEV_THROTTLING_LOW
ssize_t blk_throtl_sample_time_show(struct request_queue *q, char *page)
{
	if (!q->td)
		return -EINVAL;
	return sprintf(page, "%u\n", jiffies_to_msecs(q->td->throtl_slice));
}

ssize_t blk_throtl_sample_time_store(struct request_queue *q,
	const char *page, size_t count)
{
	unsigned long v;
	unsigned long t;

	if (!q->td)
		return -EINVAL;
	if (kstrtoul(page, 10, &v))
		return -EINVAL;
	t = msecs_to_jiffies(v);
	if (t == 0 || t > MAX_THROTL_SLICE)
		return -EINVAL;
	q->td->throtl_slice = t;
	return count;
}
#endif

2662 2663
static int __init throtl_init(void)
{
2664 2665 2666 2667
	kthrotld_workqueue = alloc_workqueue("kthrotld", WQ_MEM_RECLAIM, 0);
	if (!kthrotld_workqueue)
		panic("Failed to create kthrotld\n");

T
Tejun Heo 已提交
2668
	return blkcg_policy_register(&blkcg_policy_throtl);
2669 2670 2671
}

module_init(throtl_init);