path: root/block/blk-throttle.c (plain)
blob: 3a4c9a3c1427fc7802c5dee58d131ed6aa638b91

1	/*
2	* Interface for controlling IO bandwidth on a request queue
3	*
4	* Copyright (C) 2010 Vivek Goyal <vgoyal@redhat.com>
5	*/
6
7	#include <linux/module.h>
8	#include <linux/slab.h>
9	#include <linux/blkdev.h>
10	#include <linux/bio.h>
11	#include <linux/blktrace_api.h>
12	#include <linux/blk-cgroup.h>
13	#include "blk.h"
14
15	/* Max dispatch from a group in 1 round */
16	static int throtl_grp_quantum = 8;
17
18	/* Total max dispatch from all groups in one round */
19	static int throtl_quantum = 32;
20
21	/* Throttling is performed over 100ms slice and after that slice is renewed */
22	static unsigned long throtl_slice = HZ/10; /* 100 ms */
23
24	static struct blkcg_policy blkcg_policy_throtl;
25
26	/* A workqueue to queue throttle related work */
27	static struct workqueue_struct *kthrotld_workqueue;
28
29	/*
30	* To implement hierarchical throttling, throtl_grps form a tree and bios
31	* are dispatched upwards level by level until they reach the top and get
32	* issued. When dispatching bios from the children and local group at each
33	* level, if the bios are dispatched into a single bio_list, there's a risk
34	* of a local or child group which can queue many bios at once filling up
35	* the list starving others.
36	*
37	* To avoid such starvation, dispatched bios are queued separately
38	* according to where they came from. When they are again dispatched to
39	* the parent, they're popped in round-robin order so that no single source
40	* hogs the dispatch window.
41	*
42	* throtl_qnode is used to keep the queued bios separated by their sources.
43	* Bios are queued to throtl_qnode which in turn is queued to
44	* throtl_service_queue and then dispatched in round-robin order.
45	*
46	* It's also used to track the reference counts on blkg's. A qnode always
47	* belongs to a throtl_grp and gets queued on itself or the parent, so
48	* incrementing the reference of the associated throtl_grp when a qnode is
49	* queued and decrementing when dequeued is enough to keep the whole blkg
50	* tree pinned while bios are in flight.
51	*/
52	struct throtl_qnode {
53	struct list_head node; /* service_queue->queued[] */
54	struct bio_list bios; /* queued bios */
55	struct throtl_grp *tg; /* tg this qnode belongs to */
56	};
57
58	struct throtl_service_queue {
59	struct throtl_service_queue *parent_sq; /* the parent service_queue */
60
61	/*
62	* Bios queued directly to this service_queue or dispatched from
63	* children throtl_grp's.
64	*/
65	struct list_head queued[2]; /* throtl_qnode [READ/WRITE] */
66	unsigned int nr_queued[2]; /* number of queued bios */
67
68	/*
69	* RB tree of active children throtl_grp's, which are sorted by
70	* their ->disptime.
71	*/
72	struct rb_root pending_tree; /* RB tree of active tgs */
73	struct rb_node *first_pending; /* first node in the tree */
74	unsigned int nr_pending; /* # queued in the tree */
75	unsigned long first_pending_disptime; /* disptime of the first tg */
76	struct timer_list pending_timer; /* fires on first_pending_disptime */
77	};
78
79	enum tg_state_flags {
80	THROTL_TG_PENDING = 1 << 0, /* on parent's pending tree */
81	THROTL_TG_WAS_EMPTY = 1 << 1, /* bio_lists[] became non-empty */
82	};
83
84	#define rb_entry_tg(node) rb_entry((node), struct throtl_grp, rb_node)
85
86	struct throtl_grp {
87	/* must be the first member */
88	struct blkg_policy_data pd;
89
90	/* active throtl group service_queue member */
91	struct rb_node rb_node;
92
93	/* throtl_data this group belongs to */
94	struct throtl_data *td;
95
96	/* this group's service queue */
97	struct throtl_service_queue service_queue;
98
99	/*
100	* qnode_on_self is used when bios are directly queued to this
101	* throtl_grp so that local bios compete fairly with bios
102	* dispatched from children. qnode_on_parent is used when bios are
103	* dispatched from this throtl_grp into its parent and will compete
104	* with the sibling qnode_on_parents and the parent's
105	* qnode_on_self.
106	*/
107	struct throtl_qnode qnode_on_self[2];
108	struct throtl_qnode qnode_on_parent[2];
109
110	/*
111	* Dispatch time in jiffies. This is the estimated time when group
112	* will unthrottle and is ready to dispatch more bio. It is used as
113	* key to sort active groups in service tree.
114	*/
115	unsigned long disptime;
116
117	unsigned int flags;
118
119	/* are there any throtl rules between this group and td? */
120	bool has_rules[2];
121
122	/* bytes per second rate limits */
123	uint64_t bps[2];
124
125	/* IOPS limits */
126	unsigned int iops[2];
127
128	/* Number of bytes disptached in current slice */
129	uint64_t bytes_disp[2];
130	/* Number of bio's dispatched in current slice */
131	unsigned int io_disp[2];
132
133	/* When did we start a new slice */
134	unsigned long slice_start[2];
135	unsigned long slice_end[2];
136	};
137
138	struct throtl_data
139	{
140	/* service tree for active throtl groups */
141	struct throtl_service_queue service_queue;
142
143	struct request_queue *queue;
144
145	/* Total Number of queued bios on READ and WRITE lists */
146	unsigned int nr_queued[2];
147
148	/* Work for dispatching throttled bios */
149	struct work_struct dispatch_work;
150	};
151
152	static void throtl_pending_timer_fn(unsigned long arg);
153
154	static inline struct throtl_grp *pd_to_tg(struct blkg_policy_data *pd)
155	{
156	return pd ? container_of(pd, struct throtl_grp, pd) : NULL;
157	}
158
159	static inline struct throtl_grp *blkg_to_tg(struct blkcg_gq *blkg)
160	{
161	return pd_to_tg(blkg_to_pd(blkg, &blkcg_policy_throtl));
162	}
163
164	static inline struct blkcg_gq *tg_to_blkg(struct throtl_grp *tg)
165	{
166	return pd_to_blkg(&tg->pd);
167	}
168
169	/**
170	* sq_to_tg - return the throl_grp the specified service queue belongs to
171	* @sq: the throtl_service_queue of interest
172	*
173	* Return the throtl_grp @sq belongs to. If @sq is the top-level one
174	* embedded in throtl_data, %NULL is returned.
175	*/
176	static struct throtl_grp *sq_to_tg(struct throtl_service_queue *sq)
177	{
178	if (sq && sq->parent_sq)
179	return container_of(sq, struct throtl_grp, service_queue);
180	else
181	return NULL;
182	}
183
184	/**
185	* sq_to_td - return throtl_data the specified service queue belongs to
186	* @sq: the throtl_service_queue of interest
187	*
188	* A service_queue can be embeded in either a throtl_grp or throtl_data.
189	* Determine the associated throtl_data accordingly and return it.
190	*/
191	static struct throtl_data *sq_to_td(struct throtl_service_queue *sq)
192	{
193	struct throtl_grp *tg = sq_to_tg(sq);
194
195	if (tg)
196	return tg->td;
197	else
198	return container_of(sq, struct throtl_data, service_queue);
199	}
200
201	/**
202	* throtl_log - log debug message via blktrace
203	* @sq: the service_queue being reported
204	* @fmt: printf format string
205	* @args: printf args
206	*
207	* The messages are prefixed with "throtl BLKG_NAME" if @sq belongs to a
208	* throtl_grp; otherwise, just "throtl".
209	*/
210	#define throtl_log(sq, fmt, args...) do { \
211	struct throtl_grp *__tg = sq_to_tg((sq)); \
212	struct throtl_data *__td = sq_to_td((sq)); \
213	\
214	(void)__td; \
215	if (likely(!blk_trace_note_message_enabled(__td->queue))) \
216	break; \
217	if ((__tg)) { \
218	char __pbuf[128]; \
219	\
220	blkg_path(tg_to_blkg(__tg), __pbuf, sizeof(__pbuf)); \
221	blk_add_trace_msg(__td->queue, "throtl %s " fmt, __pbuf, ##args); \
222	} else { \
223	blk_add_trace_msg(__td->queue, "throtl " fmt, ##args); \
224	} \
225	} while (0)
226
227	static void throtl_qnode_init(struct throtl_qnode *qn, struct throtl_grp *tg)
228	{
229	INIT_LIST_HEAD(&qn->node);
230	bio_list_init(&qn->bios);
231	qn->tg = tg;
232	}
233
234	/**
235	* throtl_qnode_add_bio - add a bio to a throtl_qnode and activate it
236	* @bio: bio being added
237	* @qn: qnode to add bio to
238	* @queued: the service_queue->queued[] list @qn belongs to
239	*
240	* Add @bio to @qn and put @qn on @queued if it's not already on.
241	* @qn->tg's reference count is bumped when @qn is activated. See the
242	* comment on top of throtl_qnode definition for details.
243	*/
244	static void throtl_qnode_add_bio(struct bio *bio, struct throtl_qnode *qn,
245	struct list_head *queued)
246	{
247	bio_list_add(&qn->bios, bio);
248	if (list_empty(&qn->node)) {
249	list_add_tail(&qn->node, queued);
250	blkg_get(tg_to_blkg(qn->tg));
251	}
252	}
253
254	/**
255	* throtl_peek_queued - peek the first bio on a qnode list
256	* @queued: the qnode list to peek
257	*/
258	static struct bio *throtl_peek_queued(struct list_head *queued)
259	{
260	struct throtl_qnode *qn = list_first_entry(queued, struct throtl_qnode, node);
261	struct bio *bio;
262
263	if (list_empty(queued))
264	return NULL;
265
266	bio = bio_list_peek(&qn->bios);
267	WARN_ON_ONCE(!bio);
268	return bio;
269	}
270
271	/**
272	* throtl_pop_queued - pop the first bio form a qnode list
273	* @queued: the qnode list to pop a bio from
274	* @tg_to_put: optional out argument for throtl_grp to put
275	*
276	* Pop the first bio from the qnode list @queued. After popping, the first
277	* qnode is removed from @queued if empty or moved to the end of @queued so
278	* that the popping order is round-robin.
279	*
280	* When the first qnode is removed, its associated throtl_grp should be put
281	* too. If @tg_to_put is NULL, this function automatically puts it;
282	* otherwise, *@tg_to_put is set to the throtl_grp to put and the caller is
283	* responsible for putting it.
284	*/
285	static struct bio *throtl_pop_queued(struct list_head *queued,
286	struct throtl_grp **tg_to_put)
287	{
288	struct throtl_qnode *qn = list_first_entry(queued, struct throtl_qnode, node);
289	struct bio *bio;
290
291	if (list_empty(queued))
292	return NULL;
293
294	bio = bio_list_pop(&qn->bios);
295	WARN_ON_ONCE(!bio);
296
297	if (bio_list_empty(&qn->bios)) {
298	list_del_init(&qn->node);
299	if (tg_to_put)
300	*tg_to_put = qn->tg;
301	else
302	blkg_put(tg_to_blkg(qn->tg));
303	} else {
304	list_move_tail(&qn->node, queued);
305	}
306
307	return bio;
308	}
309
310	/* init a service_queue, assumes the caller zeroed it */
311	static void throtl_service_queue_init(struct throtl_service_queue *sq)
312	{
313	INIT_LIST_HEAD(&sq->queued[0]);
314	INIT_LIST_HEAD(&sq->queued[1]);
315	sq->pending_tree = RB_ROOT;
316	setup_timer(&sq->pending_timer, throtl_pending_timer_fn,
317	(unsigned long)sq);
318	}
319
320	static struct blkg_policy_data *throtl_pd_alloc(gfp_t gfp, int node)
321	{
322	struct throtl_grp *tg;
323	int rw;
324
325	tg = kzalloc_node(sizeof(*tg), gfp, node);
326	if (!tg)
327	return NULL;
328
329	throtl_service_queue_init(&tg->service_queue);
330
331	for (rw = READ; rw <= WRITE; rw++) {
332	throtl_qnode_init(&tg->qnode_on_self[rw], tg);
333	throtl_qnode_init(&tg->qnode_on_parent[rw], tg);
334	}
335
336	RB_CLEAR_NODE(&tg->rb_node);
337	tg->bps[READ] = -1;
338	tg->bps[WRITE] = -1;
339	tg->iops[READ] = -1;
340	tg->iops[WRITE] = -1;
341
342	return &tg->pd;
343	}
344
345	static void throtl_pd_init(struct blkg_policy_data *pd)
346	{
347	struct throtl_grp *tg = pd_to_tg(pd);
348	struct blkcg_gq *blkg = tg_to_blkg(tg);
349	struct throtl_data *td = blkg->q->td;
350	struct throtl_service_queue *sq = &tg->service_queue;
351
352	/*
353	* If on the default hierarchy, we switch to properly hierarchical
354	* behavior where limits on a given throtl_grp are applied to the
355	* whole subtree rather than just the group itself. e.g. If 16M
356	* read_bps limit is set on the root group, the whole system can't
357	* exceed 16M for the device.
358	*
359	* If not on the default hierarchy, the broken flat hierarchy
360	* behavior is retained where all throtl_grps are treated as if
361	* they're all separate root groups right below throtl_data.
362	* Limits of a group don't interact with limits of other groups
363	* regardless of the position of the group in the hierarchy.
364	*/
365	sq->parent_sq = &td->service_queue;
366	if (cgroup_subsys_on_dfl(io_cgrp_subsys) && blkg->parent)
367	sq->parent_sq = &blkg_to_tg(blkg->parent)->service_queue;
368	tg->td = td;
369	}
370
371	/*
372	* Set has_rules[] if @tg or any of its parents have limits configured.
373	* This doesn't require walking up to the top of the hierarchy as the
374	* parent's has_rules[] is guaranteed to be correct.
375	*/
376	static void tg_update_has_rules(struct throtl_grp *tg)
377	{
378	struct throtl_grp *parent_tg = sq_to_tg(tg->service_queue.parent_sq);
379	int rw;
380
381	for (rw = READ; rw <= WRITE; rw++)
382	tg->has_rules[rw] = (parent_tg && parent_tg->has_rules[rw]) ||
383	(tg->bps[rw] != -1 || tg->iops[rw] != -1);
384	}
385
386	static void throtl_pd_online(struct blkg_policy_data *pd)
387	{
388	/*
389	* We don't want new groups to escape the limits of its ancestors.
390	* Update has_rules[] after a new group is brought online.
391	*/
392	tg_update_has_rules(pd_to_tg(pd));
393	}
394
395	static void throtl_pd_free(struct blkg_policy_data *pd)
396	{
397	struct throtl_grp *tg = pd_to_tg(pd);
398
399	del_timer_sync(&tg->service_queue.pending_timer);
400	kfree(tg);
401	}
402
403	static struct throtl_grp *
404	throtl_rb_first(struct throtl_service_queue *parent_sq)
405	{
406	/* Service tree is empty */
407	if (!parent_sq->nr_pending)
408	return NULL;
409
410	if (!parent_sq->first_pending)
411	parent_sq->first_pending = rb_first(&parent_sq->pending_tree);
412
413	if (parent_sq->first_pending)
414	return rb_entry_tg(parent_sq->first_pending);
415
416	return NULL;
417	}
418
419	static void rb_erase_init(struct rb_node *n, struct rb_root *root)
420	{
421	rb_erase(n, root);
422	RB_CLEAR_NODE(n);
423	}
424
425	static void throtl_rb_erase(struct rb_node *n,
426	struct throtl_service_queue *parent_sq)
427	{
428	if (parent_sq->first_pending == n)
429	parent_sq->first_pending = NULL;
430	rb_erase_init(n, &parent_sq->pending_tree);
431	--parent_sq->nr_pending;
432	}
433
434	static void update_min_dispatch_time(struct throtl_service_queue *parent_sq)
435	{
436	struct throtl_grp *tg;
437
438	tg = throtl_rb_first(parent_sq);
439	if (!tg)
440	return;
441
442	parent_sq->first_pending_disptime = tg->disptime;
443	}
444
445	static void tg_service_queue_add(struct throtl_grp *tg)
446	{
447	struct throtl_service_queue *parent_sq = tg->service_queue.parent_sq;
448	struct rb_node **node = &parent_sq->pending_tree.rb_node;
449	struct rb_node *parent = NULL;
450	struct throtl_grp *__tg;
451	unsigned long key = tg->disptime;
452	int left = 1;
453
454	while (*node != NULL) {
455	parent = *node;
456	__tg = rb_entry_tg(parent);
457
458	if (time_before(key, __tg->disptime))
459	node = &parent->rb_left;
460	else {
461	node = &parent->rb_right;
462	left = 0;
463	}
464	}
465
466	if (left)
467	parent_sq->first_pending = &tg->rb_node;
468
469	rb_link_node(&tg->rb_node, parent, node);
470	rb_insert_color(&tg->rb_node, &parent_sq->pending_tree);
471	}
472
473	static void __throtl_enqueue_tg(struct throtl_grp *tg)
474	{
475	tg_service_queue_add(tg);
476	tg->flags |= THROTL_TG_PENDING;
477	tg->service_queue.parent_sq->nr_pending++;
478	}
479
480	static void throtl_enqueue_tg(struct throtl_grp *tg)
481	{
482	if (!(tg->flags & THROTL_TG_PENDING))
483	__throtl_enqueue_tg(tg);
484	}
485
486	static void __throtl_dequeue_tg(struct throtl_grp *tg)
487	{
488	throtl_rb_erase(&tg->rb_node, tg->service_queue.parent_sq);
489	tg->flags &= ~THROTL_TG_PENDING;
490	}
491
492	static void throtl_dequeue_tg(struct throtl_grp *tg)
493	{
494	if (tg->flags & THROTL_TG_PENDING)
495	__throtl_dequeue_tg(tg);
496	}
497
498	/* Call with queue lock held */
499	static void throtl_schedule_pending_timer(struct throtl_service_queue *sq,
500	unsigned long expires)
501	{
502	unsigned long max_expire = jiffies + 8 * throtl_slice;
503
504	/*
505	* Since we are adjusting the throttle limit dynamically, the sleep
506	* time calculated according to previous limit might be invalid. It's
507	* possible the cgroup sleep time is very long and no other cgroups
508	* have IO running so notify the limit changes. Make sure the cgroup
509	* doesn't sleep too long to avoid the missed notification.
510	*/
511	if (time_after(expires, max_expire))
512	expires = max_expire;
513	mod_timer(&sq->pending_timer, expires);
514	throtl_log(sq, "schedule timer. delay=%lu jiffies=%lu",
515	expires - jiffies, jiffies);
516	}
517
518	/**
519	* throtl_schedule_next_dispatch - schedule the next dispatch cycle
520	* @sq: the service_queue to schedule dispatch for
521	* @force: force scheduling
522	*
523	* Arm @sq->pending_timer so that the next dispatch cycle starts on the
524	* dispatch time of the first pending child. Returns %true if either timer
525	* is armed or there's no pending child left. %false if the current
526	* dispatch window is still open and the caller should continue
527	* dispatching.
528	*
529	* If @force is %true, the dispatch timer is always scheduled and this
530	* function is guaranteed to return %true. This is to be used when the
531	* caller can't dispatch itself and needs to invoke pending_timer
532	* unconditionally. Note that forced scheduling is likely to induce short
533	* delay before dispatch starts even if @sq->first_pending_disptime is not
534	* in the future and thus shouldn't be used in hot paths.
535	*/
536	static bool throtl_schedule_next_dispatch(struct throtl_service_queue *sq,
537	bool force)
538	{
539	/* any pending children left? */
540	if (!sq->nr_pending)
541	return true;
542
543	update_min_dispatch_time(sq);
544
545	/* is the next dispatch time in the future? */
546	if (force || time_after(sq->first_pending_disptime, jiffies)) {
547	throtl_schedule_pending_timer(sq, sq->first_pending_disptime);
548	return true;
549	}
550
551	/* tell the caller to continue dispatching */
552	return false;
553	}
554
555	static inline void throtl_start_new_slice_with_credit(struct throtl_grp *tg,
556	bool rw, unsigned long start)
557	{
558	tg->bytes_disp[rw] = 0;
559	tg->io_disp[rw] = 0;
560
561	/*
562	* Previous slice has expired. We must have trimmed it after last
563	* bio dispatch. That means since start of last slice, we never used
564	* that bandwidth. Do try to make use of that bandwidth while giving
565	* credit.
566	*/
567	if (time_after_eq(start, tg->slice_start[rw]))
568	tg->slice_start[rw] = start;
569
570	tg->slice_end[rw] = jiffies + throtl_slice;
571	throtl_log(&tg->service_queue,
572	"[%c] new slice with credit start=%lu end=%lu jiffies=%lu",
573	rw == READ ? 'R' : 'W', tg->slice_start[rw],
574	tg->slice_end[rw], jiffies);
575	}
576
577	static inline void throtl_start_new_slice(struct throtl_grp *tg, bool rw)
578	{
579	tg->bytes_disp[rw] = 0;
580	tg->io_disp[rw] = 0;
581	tg->slice_start[rw] = jiffies;
582	tg->slice_end[rw] = jiffies + throtl_slice;
583	throtl_log(&tg->service_queue,
584	"[%c] new slice start=%lu end=%lu jiffies=%lu",
585	rw == READ ? 'R' : 'W', tg->slice_start[rw],
586	tg->slice_end[rw], jiffies);
587	}
588
589	static inline void throtl_set_slice_end(struct throtl_grp *tg, bool rw,
590	unsigned long jiffy_end)
591	{
592	tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
593	}
594
595	static inline void throtl_extend_slice(struct throtl_grp *tg, bool rw,
596	unsigned long jiffy_end)
597	{
598	tg->slice_end[rw] = roundup(jiffy_end, throtl_slice);
599	throtl_log(&tg->service_queue,
600	"[%c] extend slice start=%lu end=%lu jiffies=%lu",
601	rw == READ ? 'R' : 'W', tg->slice_start[rw],
602	tg->slice_end[rw], jiffies);
603	}
604
605	/* Determine if previously allocated or extended slice is complete or not */
606	static bool throtl_slice_used(struct throtl_grp *tg, bool rw)
607	{
608	if (time_in_range(jiffies, tg->slice_start[rw], tg->slice_end[rw]))
609	return false;
610
611	return 1;
612	}
613
614	/* Trim the used slices and adjust slice start accordingly */
615	static inline void throtl_trim_slice(struct throtl_grp *tg, bool rw)
616	{
617	unsigned long nr_slices, time_elapsed, io_trim;
618	u64 bytes_trim, tmp;
619
620	BUG_ON(time_before(tg->slice_end[rw], tg->slice_start[rw]));
621
622	/*
623	* If bps are unlimited (-1), then time slice don't get
624	* renewed. Don't try to trim the slice if slice is used. A new
625	* slice will start when appropriate.
626	*/
627	if (throtl_slice_used(tg, rw))
628	return;
629
630	/*
631	* A bio has been dispatched. Also adjust slice_end. It might happen
632	* that initially cgroup limit was very low resulting in high
633	* slice_end, but later limit was bumped up and bio was dispached
634	* sooner, then we need to reduce slice_end. A high bogus slice_end
635	* is bad because it does not allow new slice to start.
636	*/
637
638	throtl_set_slice_end(tg, rw, jiffies + throtl_slice);
639
640	time_elapsed = jiffies - tg->slice_start[rw];
641
642	nr_slices = time_elapsed / throtl_slice;
643
644	if (!nr_slices)
645	return;
646	tmp = tg->bps[rw] * throtl_slice * nr_slices;
647	do_div(tmp, HZ);
648	bytes_trim = tmp;
649
650	io_trim = (tg->iops[rw] * throtl_slice * nr_slices)/HZ;
651
652	if (!bytes_trim && !io_trim)
653	return;
654
655	if (tg->bytes_disp[rw] >= bytes_trim)
656	tg->bytes_disp[rw] -= bytes_trim;
657	else
658	tg->bytes_disp[rw] = 0;
659
660	if (tg->io_disp[rw] >= io_trim)
661	tg->io_disp[rw] -= io_trim;
662	else
663	tg->io_disp[rw] = 0;
664
665	tg->slice_start[rw] += nr_slices * throtl_slice;
666
667	throtl_log(&tg->service_queue,
668	"[%c] trim slice nr=%lu bytes=%llu io=%lu start=%lu end=%lu jiffies=%lu",
669	rw == READ ? 'R' : 'W', nr_slices, bytes_trim, io_trim,
670	tg->slice_start[rw], tg->slice_end[rw], jiffies);
671	}
672
673	static bool tg_with_in_iops_limit(struct throtl_grp *tg, struct bio *bio,
674	unsigned long *wait)
675	{
676	bool rw = bio_data_dir(bio);
677	unsigned int io_allowed;
678	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
679	u64 tmp;
680
681	jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
682
683	/* Slice has just started. Consider one slice interval */
684	if (!jiffy_elapsed)
685	jiffy_elapsed_rnd = throtl_slice;
686
687	jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
688
689	/*
690	* jiffy_elapsed_rnd should not be a big value as minimum iops can be
691	* 1 then at max jiffy elapsed should be equivalent of 1 second as we
692	* will allow dispatch after 1 second and after that slice should
693	* have been trimmed.
694	*/
695
696	tmp = (u64)tg->iops[rw] * jiffy_elapsed_rnd;
697	do_div(tmp, HZ);
698
699	if (tmp > UINT_MAX)
700	io_allowed = UINT_MAX;
701	else
702	io_allowed = tmp;
703
704	if (tg->io_disp[rw] + 1 <= io_allowed) {
705	if (wait)
706	*wait = 0;
707	return true;
708	}
709
710	/* Calc approx time to dispatch */
711	jiffy_wait = ((tg->io_disp[rw] + 1) * HZ)/tg->iops[rw] + 1;
712
713	if (jiffy_wait > jiffy_elapsed)
714	jiffy_wait = jiffy_wait - jiffy_elapsed;
715	else
716	jiffy_wait = 1;
717
718	if (wait)
719	*wait = jiffy_wait;
720	return 0;
721	}
722
723	static bool tg_with_in_bps_limit(struct throtl_grp *tg, struct bio *bio,
724	unsigned long *wait)
725	{
726	bool rw = bio_data_dir(bio);
727	u64 bytes_allowed, extra_bytes, tmp;
728	unsigned long jiffy_elapsed, jiffy_wait, jiffy_elapsed_rnd;
729
730	jiffy_elapsed = jiffy_elapsed_rnd = jiffies - tg->slice_start[rw];
731
732	/* Slice has just started. Consider one slice interval */
733	if (!jiffy_elapsed)
734	jiffy_elapsed_rnd = throtl_slice;
735
736	jiffy_elapsed_rnd = roundup(jiffy_elapsed_rnd, throtl_slice);
737
738	tmp = tg->bps[rw] * jiffy_elapsed_rnd;
739	do_div(tmp, HZ);
740	bytes_allowed = tmp;
741
742	if (tg->bytes_disp[rw] + bio->bi_iter.bi_size <= bytes_allowed) {
743	if (wait)
744	*wait = 0;
745	return true;
746	}
747
748	/* Calc approx time to dispatch */
749	extra_bytes = tg->bytes_disp[rw] + bio->bi_iter.bi_size - bytes_allowed;
750	jiffy_wait = div64_u64(extra_bytes * HZ, tg->bps[rw]);
751
752	if (!jiffy_wait)
753	jiffy_wait = 1;
754
755	/*
756	* This wait time is without taking into consideration the rounding
757	* up we did. Add that time also.
758	*/
759	jiffy_wait = jiffy_wait + (jiffy_elapsed_rnd - jiffy_elapsed);
760	if (wait)
761	*wait = jiffy_wait;
762	return 0;
763	}
764
765	/*
766	* Returns whether one can dispatch a bio or not. Also returns approx number
767	* of jiffies to wait before this bio is with-in IO rate and can be dispatched
768	*/
769	static bool tg_may_dispatch(struct throtl_grp *tg, struct bio *bio,
770	unsigned long *wait)
771	{
772	bool rw = bio_data_dir(bio);
773	unsigned long bps_wait = 0, iops_wait = 0, max_wait = 0;
774
775	/*
776	* Currently whole state machine of group depends on first bio
777	* queued in the group bio list. So one should not be calling
778	* this function with a different bio if there are other bios
779	* queued.
780	*/
781	BUG_ON(tg->service_queue.nr_queued[rw] &&
782	bio != throtl_peek_queued(&tg->service_queue.queued[rw]));
783
784	/* If tg->bps = -1, then BW is unlimited */
785	if (tg->bps[rw] == -1 && tg->iops[rw] == -1) {
786	if (wait)
787	*wait = 0;
788	return true;
789	}
790
791	/*
792	* If previous slice expired, start a new one otherwise renew/extend
793	* existing slice to make sure it is at least throtl_slice interval
794	* long since now. New slice is started only for empty throttle group.
795	* If there is queued bio, that means there should be an active
796	* slice and it should be extended instead.
797	*/
798	if (throtl_slice_used(tg, rw) && !(tg->service_queue.nr_queued[rw]))
799	throtl_start_new_slice(tg, rw);
800	else {
801	if (time_before(tg->slice_end[rw], jiffies + throtl_slice))
802	throtl_extend_slice(tg, rw, jiffies + throtl_slice);
803	}
804
805	if (tg_with_in_bps_limit(tg, bio, &bps_wait) &&
806	tg_with_in_iops_limit(tg, bio, &iops_wait)) {
807	if (wait)
808	*wait = 0;
809	return 1;
810	}
811
812	max_wait = max(bps_wait, iops_wait);
813
814	if (wait)
815	*wait = max_wait;
816
817	if (time_before(tg->slice_end[rw], jiffies + max_wait))
818	throtl_extend_slice(tg, rw, jiffies + max_wait);
819
820	return 0;
821	}
822
823	static void throtl_charge_bio(struct throtl_grp *tg, struct bio *bio)
824	{
825	bool rw = bio_data_dir(bio);
826
827	/* Charge the bio to the group */
828	tg->bytes_disp[rw] += bio->bi_iter.bi_size;
829	tg->io_disp[rw]++;
830
831	/*
832	* REQ_THROTTLED is used to prevent the same bio to be throttled
833	* more than once as a throttled bio will go through blk-throtl the
834	* second time when it eventually gets issued. Set it when a bio
835	* is being charged to a tg.
836	*/
837	if (!(bio->bi_opf & REQ_THROTTLED))
838	bio->bi_opf |= REQ_THROTTLED;
839	}
840
841	/**
842	* throtl_add_bio_tg - add a bio to the specified throtl_grp
843	* @bio: bio to add
844	* @qn: qnode to use
845	* @tg: the target throtl_grp
846	*
847	* Add @bio to @tg's service_queue using @qn. If @qn is not specified,
848	* tg->qnode_on_self[] is used.
849	*/
850	static void throtl_add_bio_tg(struct bio *bio, struct throtl_qnode *qn,
851	struct throtl_grp *tg)
852	{
853	struct throtl_service_queue *sq = &tg->service_queue;
854	bool rw = bio_data_dir(bio);
855
856	if (!qn)
857	qn = &tg->qnode_on_self[rw];
858
859	/*
860	* If @tg doesn't currently have any bios queued in the same
861	* direction, queueing @bio can change when @tg should be
862	* dispatched. Mark that @tg was empty. This is automatically
863	* cleaered on the next tg_update_disptime().
864	*/
865	if (!sq->nr_queued[rw])
866	tg->flags |= THROTL_TG_WAS_EMPTY;
867
868	throtl_qnode_add_bio(bio, qn, &sq->queued[rw]);
869
870	sq->nr_queued[rw]++;
871	throtl_enqueue_tg(tg);
872	}
873
874	static void tg_update_disptime(struct throtl_grp *tg)
875	{
876	struct throtl_service_queue *sq = &tg->service_queue;
877	unsigned long read_wait = -1, write_wait = -1, min_wait = -1, disptime;
878	struct bio *bio;
879
880	if ((bio = throtl_peek_queued(&sq->queued[READ])))
881	tg_may_dispatch(tg, bio, &read_wait);
882
883	if ((bio = throtl_peek_queued(&sq->queued[WRITE])))
884	tg_may_dispatch(tg, bio, &write_wait);
885
886	min_wait = min(read_wait, write_wait);
887	disptime = jiffies + min_wait;
888
889	/* Update dispatch time */
890	throtl_dequeue_tg(tg);
891	tg->disptime = disptime;
892	throtl_enqueue_tg(tg);
893
894	/* see throtl_add_bio_tg() */
895	tg->flags &= ~THROTL_TG_WAS_EMPTY;
896	}
897
898	static void start_parent_slice_with_credit(struct throtl_grp *child_tg,
899	struct throtl_grp *parent_tg, bool rw)
900	{
901	if (throtl_slice_used(parent_tg, rw)) {
902	throtl_start_new_slice_with_credit(parent_tg, rw,
903	child_tg->slice_start[rw]);
904	}
905
906	}
907
908	static void tg_dispatch_one_bio(struct throtl_grp *tg, bool rw)
909	{
910	struct throtl_service_queue *sq = &tg->service_queue;
911	struct throtl_service_queue *parent_sq = sq->parent_sq;
912	struct throtl_grp *parent_tg = sq_to_tg(parent_sq);
913	struct throtl_grp *tg_to_put = NULL;
914	struct bio *bio;
915
916	/*
917	* @bio is being transferred from @tg to @parent_sq. Popping a bio
918	* from @tg may put its reference and @parent_sq might end up
919	* getting released prematurely. Remember the tg to put and put it
920	* after @bio is transferred to @parent_sq.
921	*/
922	bio = throtl_pop_queued(&sq->queued[rw], &tg_to_put);
923	sq->nr_queued[rw]--;
924
925	throtl_charge_bio(tg, bio);
926
927	/*
928	* If our parent is another tg, we just need to transfer @bio to
929	* the parent using throtl_add_bio_tg(). If our parent is
930	* @td->service_queue, @bio is ready to be issued. Put it on its
931	* bio_lists[] and decrease total number queued. The caller is
932	* responsible for issuing these bios.
933	*/
934	if (parent_tg) {
935	throtl_add_bio_tg(bio, &tg->qnode_on_parent[rw], parent_tg);
936	start_parent_slice_with_credit(tg, parent_tg, rw);
937	} else {
938	throtl_qnode_add_bio(bio, &tg->qnode_on_parent[rw],
939	&parent_sq->queued[rw]);
940	BUG_ON(tg->td->nr_queued[rw] <= 0);
941	tg->td->nr_queued[rw]--;
942	}
943
944	throtl_trim_slice(tg, rw);
945
946	if (tg_to_put)
947	blkg_put(tg_to_blkg(tg_to_put));
948	}
949
950	static int throtl_dispatch_tg(struct throtl_grp *tg)
951	{
952	struct throtl_service_queue *sq = &tg->service_queue;
953	unsigned int nr_reads = 0, nr_writes = 0;
954	unsigned int max_nr_reads = throtl_grp_quantum*3/4;
955	unsigned int max_nr_writes = throtl_grp_quantum - max_nr_reads;
956	struct bio *bio;
957
958	/* Try to dispatch 75% READS and 25% WRITES */
959
960	while ((bio = throtl_peek_queued(&sq->queued[READ])) &&
961	tg_may_dispatch(tg, bio, NULL)) {
962
963	tg_dispatch_one_bio(tg, bio_data_dir(bio));
964	nr_reads++;
965
966	if (nr_reads >= max_nr_reads)
967	break;
968	}
969
970	while ((bio = throtl_peek_queued(&sq->queued[WRITE])) &&
971	tg_may_dispatch(tg, bio, NULL)) {
972
973	tg_dispatch_one_bio(tg, bio_data_dir(bio));
974	nr_writes++;
975
976	if (nr_writes >= max_nr_writes)
977	break;
978	}
979
980	return nr_reads + nr_writes;
981	}
982
983	static int throtl_select_dispatch(struct throtl_service_queue *parent_sq)
984	{
985	unsigned int nr_disp = 0;
986
987	while (1) {
988	struct throtl_grp *tg = throtl_rb_first(parent_sq);
989	struct throtl_service_queue *sq = &tg->service_queue;
990
991	if (!tg)
992	break;
993
994	if (time_before(jiffies, tg->disptime))
995	break;
996
997	throtl_dequeue_tg(tg);
998
999	nr_disp += throtl_dispatch_tg(tg);
1000
1001	if (sq->nr_queued[0] || sq->nr_queued[1])
1002	tg_update_disptime(tg);
1003
1004	if (nr_disp >= throtl_quantum)
1005	break;
1006	}
1007
1008	return nr_disp;
1009	}
1010
1011	/**
1012	* throtl_pending_timer_fn - timer function for service_queue->pending_timer
1013	* @arg: the throtl_service_queue being serviced
1014	*
1015	* This timer is armed when a child throtl_grp with active bio's become
1016	* pending and queued on the service_queue's pending_tree and expires when
1017	* the first child throtl_grp should be dispatched. This function
1018	* dispatches bio's from the children throtl_grps to the parent
1019	* service_queue.
1020	*
1021	* If the parent's parent is another throtl_grp, dispatching is propagated
1022	* by either arming its pending_timer or repeating dispatch directly. If
1023	* the top-level service_tree is reached, throtl_data->dispatch_work is
1024	* kicked so that the ready bio's are issued.
1025	*/
1026	static void throtl_pending_timer_fn(unsigned long arg)
1027	{
1028	struct throtl_service_queue *sq = (void *)arg;
1029	struct throtl_grp *tg = sq_to_tg(sq);
1030	struct throtl_data *td = sq_to_td(sq);
1031	struct request_queue *q = td->queue;
1032	struct throtl_service_queue *parent_sq;
1033	bool dispatched;
1034	int ret;
1035
1036	spin_lock_irq(q->queue_lock);
1037	again:
1038	parent_sq = sq->parent_sq;
1039	dispatched = false;
1040
1041	while (true) {
1042	throtl_log(sq, "dispatch nr_queued=%u read=%u write=%u",
1043	sq->nr_queued[READ] + sq->nr_queued[WRITE],
1044	sq->nr_queued[READ], sq->nr_queued[WRITE]);
1045
1046	ret = throtl_select_dispatch(sq);
1047	if (ret) {
1048	throtl_log(sq, "bios disp=%u", ret);
1049	dispatched = true;
1050	}
1051
1052	if (throtl_schedule_next_dispatch(sq, false))
1053	break;
1054
1055	/* this dispatch windows is still open, relax and repeat */
1056	spin_unlock_irq(q->queue_lock);
1057	cpu_relax();
1058	spin_lock_irq(q->queue_lock);
1059	}
1060
1061	if (!dispatched)
1062	goto out_unlock;
1063
1064	if (parent_sq) {
1065	/* @parent_sq is another throl_grp, propagate dispatch */
1066	if (tg->flags & THROTL_TG_WAS_EMPTY) {
1067	tg_update_disptime(tg);
1068	if (!throtl_schedule_next_dispatch(parent_sq, false)) {
1069	/* window is already open, repeat dispatching */
1070	sq = parent_sq;
1071	tg = sq_to_tg(sq);
1072	goto again;
1073	}
1074	}
1075	} else {
1076	/* reached the top-level, queue issueing */
1077	queue_work(kthrotld_workqueue, &td->dispatch_work);
1078	}
1079	out_unlock:
1080	spin_unlock_irq(q->queue_lock);
1081	}
1082
1083	/**
1084	* blk_throtl_dispatch_work_fn - work function for throtl_data->dispatch_work
1085	* @work: work item being executed
1086	*
1087	* This function is queued for execution when bio's reach the bio_lists[]
1088	* of throtl_data->service_queue. Those bio's are ready and issued by this
1089	* function.
1090	*/
1091	static void blk_throtl_dispatch_work_fn(struct work_struct *work)
1092	{
1093	struct throtl_data *td = container_of(work, struct throtl_data,
1094	dispatch_work);
1095	struct throtl_service_queue *td_sq = &td->service_queue;
1096	struct request_queue *q = td->queue;
1097	struct bio_list bio_list_on_stack;
1098	struct bio *bio;
1099	struct blk_plug plug;
1100	int rw;
1101
1102	bio_list_init(&bio_list_on_stack);
1103
1104	spin_lock_irq(q->queue_lock);
1105	for (rw = READ; rw <= WRITE; rw++)
1106	while ((bio = throtl_pop_queued(&td_sq->queued[rw], NULL)))
1107	bio_list_add(&bio_list_on_stack, bio);
1108	spin_unlock_irq(q->queue_lock);
1109
1110	if (!bio_list_empty(&bio_list_on_stack)) {
1111	blk_start_plug(&plug);
1112	while((bio = bio_list_pop(&bio_list_on_stack)))
1113	generic_make_request(bio);
1114	blk_finish_plug(&plug);
1115	}
1116	}
1117
1118	static u64 tg_prfill_conf_u64(struct seq_file *sf, struct blkg_policy_data *pd,
1119	int off)
1120	{
1121	struct throtl_grp *tg = pd_to_tg(pd);
1122	u64 v = *(u64 *)((void *)tg + off);
1123
1124	if (v == -1)
1125	return 0;
1126	return __blkg_prfill_u64(sf, pd, v);
1127	}
1128
1129	static u64 tg_prfill_conf_uint(struct seq_file *sf, struct blkg_policy_data *pd,
1130	int off)
1131	{
1132	struct throtl_grp *tg = pd_to_tg(pd);
1133	unsigned int v = *(unsigned int *)((void *)tg + off);
1134
1135	if (v == -1)
1136	return 0;
1137	return __blkg_prfill_u64(sf, pd, v);
1138	}
1139
1140	static int tg_print_conf_u64(struct seq_file *sf, void *v)
1141	{
1142	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_conf_u64,
1143	&blkcg_policy_throtl, seq_cft(sf)->private, false);
1144	return 0;
1145	}
1146
1147	static int tg_print_conf_uint(struct seq_file *sf, void *v)
1148	{
1149	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_conf_uint,
1150	&blkcg_policy_throtl, seq_cft(sf)->private, false);
1151	return 0;
1152	}
1153
1154	static void tg_conf_updated(struct throtl_grp *tg)
1155	{
1156	struct throtl_service_queue *sq = &tg->service_queue;
1157	struct cgroup_subsys_state *pos_css;
1158	struct blkcg_gq *blkg;
1159
1160	throtl_log(&tg->service_queue,
1161	"limit change rbps=%llu wbps=%llu riops=%u wiops=%u",
1162	tg->bps[READ], tg->bps[WRITE],
1163	tg->iops[READ], tg->iops[WRITE]);
1164
1165	/*
1166	* Update has_rules[] flags for the updated tg's subtree. A tg is
1167	* considered to have rules if either the tg itself or any of its
1168	* ancestors has rules. This identifies groups without any
1169	* restrictions in the whole hierarchy and allows them to bypass
1170	* blk-throttle.
1171	*/
1172	blkg_for_each_descendant_pre(blkg, pos_css, tg_to_blkg(tg))
1173	tg_update_has_rules(blkg_to_tg(blkg));
1174
1175	/*
1176	* We're already holding queue_lock and know @tg is valid. Let's
1177	* apply the new config directly.
1178	*
1179	* Restart the slices for both READ and WRITES. It might happen
1180	* that a group's limit are dropped suddenly and we don't want to
1181	* account recently dispatched IO with new low rate.
1182	*/
1183	throtl_start_new_slice(tg, 0);
1184	throtl_start_new_slice(tg, 1);
1185
1186	if (tg->flags & THROTL_TG_PENDING) {
1187	tg_update_disptime(tg);
1188	throtl_schedule_next_dispatch(sq->parent_sq, true);
1189	}
1190	}
1191
1192	static ssize_t tg_set_conf(struct kernfs_open_file *of,
1193	char *buf, size_t nbytes, loff_t off, bool is_u64)
1194	{
1195	struct blkcg *blkcg = css_to_blkcg(of_css(of));
1196	struct blkg_conf_ctx ctx;
1197	struct throtl_grp *tg;
1198	int ret;
1199	u64 v;
1200
1201	ret = blkg_conf_prep(blkcg, &blkcg_policy_throtl, buf, &ctx);
1202	if (ret)
1203	return ret;
1204
1205	ret = -EINVAL;
1206	if (sscanf(ctx.body, "%llu", &v) != 1)
1207	goto out_finish;
1208	if (!v)
1209	v = -1;
1210
1211	tg = blkg_to_tg(ctx.blkg);
1212
1213	if (is_u64)
1214	*(u64 *)((void *)tg + of_cft(of)->private) = v;
1215	else
1216	*(unsigned int *)((void *)tg + of_cft(of)->private) = v;
1217
1218	tg_conf_updated(tg);
1219	ret = 0;
1220	out_finish:
1221	blkg_conf_finish(&ctx);
1222	return ret ?: nbytes;
1223	}
1224
1225	static ssize_t tg_set_conf_u64(struct kernfs_open_file *of,
1226	char *buf, size_t nbytes, loff_t off)
1227	{
1228	return tg_set_conf(of, buf, nbytes, off, true);
1229	}
1230
1231	static ssize_t tg_set_conf_uint(struct kernfs_open_file *of,
1232	char *buf, size_t nbytes, loff_t off)
1233	{
1234	return tg_set_conf(of, buf, nbytes, off, false);
1235	}
1236
1237	static struct cftype throtl_legacy_files[] = {
1238	{
1239	.name = "throttle.read_bps_device",
1240	.private = offsetof(struct throtl_grp, bps[READ]),
1241	.seq_show = tg_print_conf_u64,
1242	.write = tg_set_conf_u64,
1243	},
1244	{
1245	.name = "throttle.write_bps_device",
1246	.private = offsetof(struct throtl_grp, bps[WRITE]),
1247	.seq_show = tg_print_conf_u64,
1248	.write = tg_set_conf_u64,
1249	},
1250	{
1251	.name = "throttle.read_iops_device",
1252	.private = offsetof(struct throtl_grp, iops[READ]),
1253	.seq_show = tg_print_conf_uint,
1254	.write = tg_set_conf_uint,
1255	},
1256	{
1257	.name = "throttle.write_iops_device",
1258	.private = offsetof(struct throtl_grp, iops[WRITE]),
1259	.seq_show = tg_print_conf_uint,
1260	.write = tg_set_conf_uint,
1261	},
1262	{
1263	.name = "throttle.io_service_bytes",
1264	.private = (unsigned long)&blkcg_policy_throtl,
1265	.seq_show = blkg_print_stat_bytes,
1266	},
1267	{
1268	.name = "throttle.io_serviced",
1269	.private = (unsigned long)&blkcg_policy_throtl,
1270	.seq_show = blkg_print_stat_ios,
1271	},
1272	{ } /* terminate */
1273	};
1274
1275	static u64 tg_prfill_max(struct seq_file *sf, struct blkg_policy_data *pd,
1276	int off)
1277	{
1278	struct throtl_grp *tg = pd_to_tg(pd);
1279	const char *dname = blkg_dev_name(pd->blkg);
1280	char bufs[4][21] = { "max", "max", "max", "max" };
1281
1282	if (!dname)
1283	return 0;
1284	if (tg->bps[READ] == -1 && tg->bps[WRITE] == -1 &&
1285	tg->iops[READ] == -1 && tg->iops[WRITE] == -1)
1286	return 0;
1287
1288	if (tg->bps[READ] != -1)
1289	snprintf(bufs[0], sizeof(bufs[0]), "%llu", tg->bps[READ]);
1290	if (tg->bps[WRITE] != -1)
1291	snprintf(bufs[1], sizeof(bufs[1]), "%llu", tg->bps[WRITE]);
1292	if (tg->iops[READ] != -1)
1293	snprintf(bufs[2], sizeof(bufs[2]), "%u", tg->iops[READ]);
1294	if (tg->iops[WRITE] != -1)
1295	snprintf(bufs[3], sizeof(bufs[3]), "%u", tg->iops[WRITE]);
1296
1297	seq_printf(sf, "%s rbps=%s wbps=%s riops=%s wiops=%s\n",
1298	dname, bufs[0], bufs[1], bufs[2], bufs[3]);
1299	return 0;
1300	}
1301
1302	static int tg_print_max(struct seq_file *sf, void *v)
1303	{
1304	blkcg_print_blkgs(sf, css_to_blkcg(seq_css(sf)), tg_prfill_max,
1305	&blkcg_policy_throtl, seq_cft(sf)->private, false);
1306	return 0;
1307	}
1308
1309	static ssize_t tg_set_max(struct kernfs_open_file *of,
1310	char *buf, size_t nbytes, loff_t off)
1311	{
1312	struct blkcg *blkcg = css_to_blkcg(of_css(of));
1313	struct blkg_conf_ctx ctx;
1314	struct throtl_grp *tg;
1315	u64 v[4];
1316	int ret;
1317
1318	ret = blkg_conf_prep(blkcg, &blkcg_policy_throtl, buf, &ctx);
1319	if (ret)
1320	return ret;
1321
1322	tg = blkg_to_tg(ctx.blkg);
1323
1324	v[0] = tg->bps[READ];
1325	v[1] = tg->bps[WRITE];
1326	v[2] = tg->iops[READ];
1327	v[3] = tg->iops[WRITE];
1328
1329	while (true) {
1330	char tok[27]; /* wiops=18446744073709551616 */
1331	char *p;
1332	u64 val = -1;
1333	int len;
1334
1335	if (sscanf(ctx.body, "%26s%n", tok, &len) != 1)
1336	break;
1337	if (tok[0] == '\0')
1338	break;
1339	ctx.body += len;
1340
1341	ret = -EINVAL;
1342	p = tok;
1343	strsep(&p, "=");
1344	if (!p || (sscanf(p, "%llu", &val) != 1 && strcmp(p, "max")))
1345	goto out_finish;
1346
1347	ret = -ERANGE;
1348	if (!val)
1349	goto out_finish;
1350
1351	ret = -EINVAL;
1352	if (!strcmp(tok, "rbps"))
1353	v[0] = val;
1354	else if (!strcmp(tok, "wbps"))
1355	v[1] = val;
1356	else if (!strcmp(tok, "riops"))
1357	v[2] = min_t(u64, val, UINT_MAX);
1358	else if (!strcmp(tok, "wiops"))
1359	v[3] = min_t(u64, val, UINT_MAX);
1360	else
1361	goto out_finish;
1362	}
1363
1364	tg->bps[READ] = v[0];
1365	tg->bps[WRITE] = v[1];
1366	tg->iops[READ] = v[2];
1367	tg->iops[WRITE] = v[3];
1368
1369	tg_conf_updated(tg);
1370	ret = 0;
1371	out_finish:
1372	blkg_conf_finish(&ctx);
1373	return ret ?: nbytes;
1374	}
1375
1376	static struct cftype throtl_files[] = {
1377	{
1378	.name = "max",
1379	.flags = CFTYPE_NOT_ON_ROOT,
1380	.seq_show = tg_print_max,
1381	.write = tg_set_max,
1382	},
1383	{ } /* terminate */
1384	};
1385
1386	static void throtl_shutdown_wq(struct request_queue *q)
1387	{
1388	struct throtl_data *td = q->td;
1389
1390	cancel_work_sync(&td->dispatch_work);
1391	}
1392
1393	static struct blkcg_policy blkcg_policy_throtl = {
1394	.dfl_cftypes = throtl_files,
1395	.legacy_cftypes = throtl_legacy_files,
1396
1397	.pd_alloc_fn = throtl_pd_alloc,
1398	.pd_init_fn = throtl_pd_init,
1399	.pd_online_fn = throtl_pd_online,
1400	.pd_free_fn = throtl_pd_free,
1401	};
1402
1403	bool blk_throtl_bio(struct request_queue *q, struct blkcg_gq *blkg,
1404	struct bio *bio)
1405	{
1406	struct throtl_qnode *qn = NULL;
1407	struct throtl_grp *tg = blkg_to_tg(blkg ?: q->root_blkg);
1408	struct throtl_service_queue *sq;
1409	bool rw = bio_data_dir(bio);
1410	bool throttled = false;
1411
1412	WARN_ON_ONCE(!rcu_read_lock_held());
1413
1414	/* see throtl_charge_bio() */
1415	if ((bio->bi_opf & REQ_THROTTLED) || !tg->has_rules[rw])
1416	goto out;
1417
1418	spin_lock_irq(q->queue_lock);
1419
1420	if (unlikely(blk_queue_bypass(q)))
1421	goto out_unlock;
1422
1423	sq = &tg->service_queue;
1424
1425	while (true) {
1426	/* throtl is FIFO - if bios are already queued, should queue */
1427	if (sq->nr_queued[rw])
1428	break;
1429
1430	/* if above limits, break to queue */
1431	if (!tg_may_dispatch(tg, bio, NULL))
1432	break;
1433
1434	/* within limits, let's charge and dispatch directly */
1435	throtl_charge_bio(tg, bio);
1436
1437	/*
1438	* We need to trim slice even when bios are not being queued
1439	* otherwise it might happen that a bio is not queued for
1440	* a long time and slice keeps on extending and trim is not
1441	* called for a long time. Now if limits are reduced suddenly
1442	* we take into account all the IO dispatched so far at new
1443	* low rate and * newly queued IO gets a really long dispatch
1444	* time.
1445	*
1446	* So keep on trimming slice even if bio is not queued.
1447	*/
1448	throtl_trim_slice(tg, rw);
1449
1450	/*
1451	* @bio passed through this layer without being throttled.
1452	* Climb up the ladder. If we''re already at the top, it
1453	* can be executed directly.
1454	*/
1455	qn = &tg->qnode_on_parent[rw];
1456	sq = sq->parent_sq;
1457	tg = sq_to_tg(sq);
1458	if (!tg)
1459	goto out_unlock;
1460	}
1461
1462	/* out-of-limit, queue to @tg */
1463	throtl_log(sq, "[%c] bio. bdisp=%llu sz=%u bps=%llu iodisp=%u iops=%u queued=%d/%d",
1464	rw == READ ? 'R' : 'W',
1465	tg->bytes_disp[rw], bio->bi_iter.bi_size, tg->bps[rw],
1466	tg->io_disp[rw], tg->iops[rw],
1467	sq->nr_queued[READ], sq->nr_queued[WRITE]);
1468
1469	bio_associate_current(bio);
1470	tg->td->nr_queued[rw]++;
1471	throtl_add_bio_tg(bio, qn, tg);
1472	throttled = true;
1473
1474	/*
1475	* Update @tg's dispatch time and force schedule dispatch if @tg
1476	* was empty before @bio. The forced scheduling isn't likely to
1477	* cause undue delay as @bio is likely to be dispatched directly if
1478	* its @tg's disptime is not in the future.
1479	*/
1480	if (tg->flags & THROTL_TG_WAS_EMPTY) {
1481	tg_update_disptime(tg);
1482	throtl_schedule_next_dispatch(tg->service_queue.parent_sq, true);
1483	}
1484
1485	out_unlock:
1486	spin_unlock_irq(q->queue_lock);
1487	out:
1488	/*
1489	* As multiple blk-throtls may stack in the same issue path, we
1490	* don't want bios to leave with the flag set. Clear the flag if
1491	* being issued.
1492	*/
1493	if (!throttled)
1494	bio->bi_opf &= ~REQ_THROTTLED;
1495	return throttled;
1496	}
1497
1498	/*
1499	* Dispatch all bios from all children tg's queued on @parent_sq. On
1500	* return, @parent_sq is guaranteed to not have any active children tg's
1501	* and all bios from previously active tg's are on @parent_sq->bio_lists[].
1502	*/
1503	static void tg_drain_bios(struct throtl_service_queue *parent_sq)
1504	{
1505	struct throtl_grp *tg;
1506
1507	while ((tg = throtl_rb_first(parent_sq))) {
1508	struct throtl_service_queue *sq = &tg->service_queue;
1509	struct bio *bio;
1510
1511	throtl_dequeue_tg(tg);
1512
1513	while ((bio = throtl_peek_queued(&sq->queued[READ])))
1514	tg_dispatch_one_bio(tg, bio_data_dir(bio));
1515	while ((bio = throtl_peek_queued(&sq->queued[WRITE])))
1516	tg_dispatch_one_bio(tg, bio_data_dir(bio));
1517	}
1518	}
1519
1520	/**
1521	* blk_throtl_drain - drain throttled bios
1522	* @q: request_queue to drain throttled bios for
1523	*
1524	* Dispatch all currently throttled bios on @q through ->make_request_fn().
1525	*/
1526	void blk_throtl_drain(struct request_queue *q)
1527	__releases(q->queue_lock) __acquires(q->queue_lock)
1528	{
1529	struct throtl_data *td = q->td;
1530	struct blkcg_gq *blkg;
1531	struct cgroup_subsys_state *pos_css;
1532	struct bio *bio;
1533	int rw;
1534
1535	queue_lockdep_assert_held(q);
1536	rcu_read_lock();
1537
1538	/*
1539	* Drain each tg while doing post-order walk on the blkg tree, so
1540	* that all bios are propagated to td->service_queue. It'd be
1541	* better to walk service_queue tree directly but blkg walk is
1542	* easier.
1543	*/
1544	blkg_for_each_descendant_post(blkg, pos_css, td->queue->root_blkg)
1545	tg_drain_bios(&blkg_to_tg(blkg)->service_queue);
1546
1547	/* finally, transfer bios from top-level tg's into the td */
1548	tg_drain_bios(&td->service_queue);
1549
1550	rcu_read_unlock();
1551	spin_unlock_irq(q->queue_lock);
1552
1553	/* all bios now should be in td->service_queue, issue them */
1554	for (rw = READ; rw <= WRITE; rw++)
1555	while ((bio = throtl_pop_queued(&td->service_queue.queued[rw],
1556	NULL)))
1557	generic_make_request(bio);
1558
1559	spin_lock_irq(q->queue_lock);
1560	}
1561
1562	int blk_throtl_init(struct request_queue *q)
1563	{
1564	struct throtl_data *td;
1565	int ret;
1566
1567	td = kzalloc_node(sizeof(*td), GFP_KERNEL, q->node);
1568	if (!td)
1569	return -ENOMEM;
1570
1571	INIT_WORK(&td->dispatch_work, blk_throtl_dispatch_work_fn);
1572	throtl_service_queue_init(&td->service_queue);
1573
1574	q->td = td;
1575	td->queue = q;
1576
1577	/* activate policy */
1578	ret = blkcg_activate_policy(q, &blkcg_policy_throtl);
1579	if (ret)
1580	kfree(td);
1581	return ret;
1582	}
1583
1584	void blk_throtl_exit(struct request_queue *q)
1585	{
1586	BUG_ON(!q->td);
1587	throtl_shutdown_wq(q);
1588	blkcg_deactivate_policy(q, &blkcg_policy_throtl);
1589	kfree(q->td);
1590	}
1591
1592	static int __init throtl_init(void)
1593	{
1594	kthrotld_workqueue = alloc_workqueue("kthrotld", WQ_MEM_RECLAIM, 0);
1595	if (!kthrotld_workqueue)
1596	panic("Failed to create kthrotld\n");
1597
1598	return blkcg_policy_register(&blkcg_policy_throtl);
1599	}
1600
1601	module_init(throtl_init);
1602