1	// SPDX-License-Identifier: GPL-2.0-or-later
2	/*
3	* net/sched/sch_api.c Packet scheduler API.
4	*
5	* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
6	*
7	* Fixes:
8	*
9	* Rani Assaf <rani@magic.metawire.com> :980802: JIFFIES and CPU clock sources are repaired.
10	* Eduardo J. Blanco <ejbs@netlabs.com.uy> :990222: kmod support
11	* Jamal Hadi Salim <hadi@nortelnetworks.com>: 990601: ingress support
12	*/
13
14	#include <linux/module.h>
15	#include <linux/types.h>
16	#include <linux/kernel.h>
17	#include <linux/string.h>
18	#include <linux/errno.h>
19	#include <linux/skbuff.h>
20	#include <linux/init.h>
21	#include <linux/proc_fs.h>
22	#include <linux/seq_file.h>
23	#include <linux/kmod.h>
24	#include <linux/list.h>
25	#include <linux/hrtimer.h>
26	#include <linux/slab.h>
27	#include <linux/hashtable.h>
28
29	#include <net/net_namespace.h>
30	#include <net/sock.h>
31	#include <net/netlink.h>
32	#include <net/pkt_sched.h>
33	#include <net/pkt_cls.h>
34	#include <net/tc_wrapper.h>
35
36	#include <trace/events/qdisc.h>
37
38	/*
39
40	Short review.
41	-------------
42
43	This file consists of two interrelated parts:
44
45	1. queueing disciplines manager frontend.
46	2. traffic classes manager frontend.
47
48	Generally, queueing discipline ("qdisc") is a black box,
49	which is able to enqueue packets and to dequeue them (when
50	device is ready to send something) in order and at times
51	determined by algorithm hidden in it.
52
53	qdisc's are divided to two categories:
54	- "queues", which have no internal structure visible from outside.
55	- "schedulers", which split all the packets to "traffic classes",
56	using "packet classifiers" (look at cls_api.c)
57
58	In turn, classes may have child qdiscs (as rule, queues)
59	attached to them etc. etc. etc.
60
61	The goal of the routines in this file is to translate
62	information supplied by user in the form of handles
63	to more intelligible for kernel form, to make some sanity
64	checks and part of work, which is common to all qdiscs
65	and to provide rtnetlink notifications.
66
67	All real intelligent work is done inside qdisc modules.
68
69
70
71	Every discipline has two major routines: enqueue and dequeue.
72
73	---dequeue
74
75	dequeue usually returns a skb to send. It is allowed to return NULL,
76	but it does not mean that queue is empty, it just means that
77	discipline does not want to send anything this time.
78	Queue is really empty if q->q.qlen == 0.
79	For complicated disciplines with multiple queues q->q is not
80	real packet queue, but however q->q.qlen must be valid.
81
82	---enqueue
83
84	enqueue returns 0, if packet was enqueued successfully.
85	If packet (this one or another one) was dropped, it returns
86	not zero error code.
87	NET_XMIT_DROP - this packet dropped
88	Expected action: do not backoff, but wait until queue will clear.
89	NET_XMIT_CN - probably this packet enqueued, but another one dropped.
90	Expected action: backoff or ignore
91
92	Auxiliary routines:
93
94	---peek
95
96	like dequeue but without removing a packet from the queue
97
98	---reset
99
100	returns qdisc to initial state: purge all buffers, clear all
101	timers, counters (except for statistics) etc.
102
103	---init
104
105	initializes newly created qdisc.
106
107	---destroy
108
109	destroys resources allocated by init and during lifetime of qdisc.
110
111	---change
112
113	changes qdisc parameters.
114	*/
115
116	/* Protects list of registered TC modules. It is pure SMP lock. */
117	static DEFINE_RWLOCK(qdisc_mod_lock);
118
119
120	/************************************************
121	* Queueing disciplines manipulation. *
122	************************************************/
123
124
125	/* The list of all installed queueing disciplines. */
126
127	static struct Qdisc_ops *qdisc_base;
128
129	/* Register/unregister queueing discipline */
130
131	int register_qdisc(struct Qdisc_ops *qops)
132	{
133	struct Qdisc_ops *q, **qp;
134	int rc = -EEXIST;
135
136	write_lock(&qdisc_mod_lock);
137	for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
138	if (!strcmp(qops->id, q->id))
139	goto out;
140
141	if (qops->enqueue == NULL)
142	qops->enqueue = noop_qdisc_ops.enqueue;
143	if (qops->peek == NULL) {
144	if (qops->dequeue == NULL)
145	qops->peek = noop_qdisc_ops.peek;
146	else
147	goto out_einval;
148	}
149	if (qops->dequeue == NULL)
150	qops->dequeue = noop_qdisc_ops.dequeue;
151
152	if (qops->cl_ops) {
153	const struct Qdisc_class_ops *cops = qops->cl_ops;
154
155	if (!(cops->find && cops->walk && cops->leaf))
156	goto out_einval;
157
158	if (cops->tcf_block && !(cops->bind_tcf && cops->unbind_tcf))
159	goto out_einval;
160	}
161
162	qops->next = NULL;
163	*qp = qops;
164	rc = 0;
165	out:
166	write_unlock(&qdisc_mod_lock);
167	return rc;
168
169	out_einval:
170	rc = -EINVAL;
171	goto out;
172	}
173	EXPORT_SYMBOL(register_qdisc);
174
175	void unregister_qdisc(struct Qdisc_ops *qops)
176	{
177	struct Qdisc_ops *q, **qp;
178	int err = -ENOENT;
179
180	write_lock(&qdisc_mod_lock);
181	for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
182	if (q == qops)
183	break;
184	if (q) {
185	*qp = q->next;
186	q->next = NULL;
187	err = 0;
188	}
189	write_unlock(&qdisc_mod_lock);
190
191	WARN(err, "unregister qdisc(%s) failed\n", qops->id);
192	}
193	EXPORT_SYMBOL(unregister_qdisc);
194
195	/* Get default qdisc if not otherwise specified */
196	void qdisc_get_default(char *name, size_t len)
197	{
198	read_lock(&qdisc_mod_lock);
199	strscpy(p: name, q: default_qdisc_ops->id, size: len);
200	read_unlock(&qdisc_mod_lock);
201	}
202
203	static struct Qdisc_ops *qdisc_lookup_default(const char *name)
204	{
205	struct Qdisc_ops *q = NULL;
206
207	for (q = qdisc_base; q; q = q->next) {
208	if (!strcmp(name, q->id)) {
209	if (!try_module_get(module: q->owner))
210	q = NULL;
211	break;
212	}
213	}
214
215	return q;
216	}
217
218	/* Set new default qdisc to use */
219	int qdisc_set_default(const char *name)
220	{
221	const struct Qdisc_ops *ops;
222
223	if (!capable(CAP_NET_ADMIN))
224	return -EPERM;
225
226	write_lock(&qdisc_mod_lock);
227	ops = qdisc_lookup_default(name);
228	if (!ops) {
229	/* Not found, drop lock and try to load module */
230	write_unlock(&qdisc_mod_lock);
231	request_module("sch_%s", name);
232	write_lock(&qdisc_mod_lock);
233
234	ops = qdisc_lookup_default(name);
235	}
236
237	if (ops) {
238	/* Set new default */
239	module_put(module: default_qdisc_ops->owner);
240	default_qdisc_ops = ops;
241	}
242	write_unlock(&qdisc_mod_lock);
243
244	return ops ? 0 : -ENOENT;
245	}
246
247	#ifdef CONFIG_NET_SCH_DEFAULT
248	/* Set default value from kernel config */
249	static int __init sch_default_qdisc(void)
250	{
251	return qdisc_set_default(CONFIG_DEFAULT_NET_SCH);
252	}
253	late_initcall(sch_default_qdisc);
254	#endif
255
256	/* We know handle. Find qdisc among all qdisc's attached to device
257	* (root qdisc, all its children, children of children etc.)
258	* Note: caller either uses rtnl or rcu_read_lock()
259	*/
260
261	static struct Qdisc *qdisc_match_from_root(struct Qdisc *root, u32 handle)
262	{
263	struct Qdisc *q;
264
265	if (!qdisc_dev(qdisc: root))
266	return (root->handle == handle ? root : NULL);
267
268	if (!(root->flags & TCQ_F_BUILTIN) &&
269	root->handle == handle)
270	return root;
271
272	hash_for_each_possible_rcu(qdisc_dev(root)->qdisc_hash, q, hash, handle,
273	lockdep_rtnl_is_held()) {
274	if (q->handle == handle)
275	return q;
276	}
277	return NULL;
278	}
279
280	void qdisc_hash_add(struct Qdisc *q, bool invisible)
281	{
282	if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
283	ASSERT_RTNL();
284	hash_add_rcu(qdisc_dev(q)->qdisc_hash, &q->hash, q->handle);
285	if (invisible)
286	q->flags |= TCQ_F_INVISIBLE;
287	}
288	}
289	EXPORT_SYMBOL(qdisc_hash_add);
290
291	void qdisc_hash_del(struct Qdisc *q)
292	{
293	if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
294	ASSERT_RTNL();
295	hash_del_rcu(node: &q->hash);
296	}
297	}
298	EXPORT_SYMBOL(qdisc_hash_del);
299
300	struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
301	{
302	struct Qdisc *q;
303
304	if (!handle)
305	return NULL;
306	q = qdisc_match_from_root(rtnl_dereference(dev->qdisc), handle);
307	if (q)
308	goto out;
309
310	if (dev_ingress_queue(dev))
311	q = qdisc_match_from_root(
312	rtnl_dereference(dev_ingress_queue(dev)->qdisc_sleeping),
313	handle);
314	out:
315	return q;
316	}
317
318	struct Qdisc *qdisc_lookup_rcu(struct net_device *dev, u32 handle)
319	{
320	struct netdev_queue *nq;
321	struct Qdisc *q;
322
323	if (!handle)
324	return NULL;
325	q = qdisc_match_from_root(rcu_dereference(dev->qdisc), handle);
326	if (q)
327	goto out;
328
329	nq = dev_ingress_queue_rcu(dev);
330	if (nq)
331	q = qdisc_match_from_root(rcu_dereference(nq->qdisc_sleeping),
332	handle);
333	out:
334	return q;
335	}
336
337	static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
338	{
339	unsigned long cl;
340	const struct Qdisc_class_ops *cops = p->ops->cl_ops;
341
342	if (cops == NULL)
343	return NULL;
344	cl = cops->find(p, classid);
345
346	if (cl == 0)
347	return NULL;
348	return cops->leaf(p, cl);
349	}
350
351	/* Find queueing discipline by name */
352
353	static struct Qdisc_ops *qdisc_lookup_ops(struct nlattr *kind)
354	{
355	struct Qdisc_ops *q = NULL;
356
357	if (kind) {
358	read_lock(&qdisc_mod_lock);
359	for (q = qdisc_base; q; q = q->next) {
360	if (nla_strcmp(nla: kind, str: q->id) == 0) {
361	if (!try_module_get(module: q->owner))
362	q = NULL;
363	break;
364	}
365	}
366	read_unlock(&qdisc_mod_lock);
367	}
368	return q;
369	}
370
371	/* The linklayer setting were not transferred from iproute2, in older
372	* versions, and the rate tables lookup systems have been dropped in
373	* the kernel. To keep backward compatible with older iproute2 tc
374	* utils, we detect the linklayer setting by detecting if the rate
375	* table were modified.
376	*
377	* For linklayer ATM table entries, the rate table will be aligned to
378	* 48 bytes, thus some table entries will contain the same value. The
379	* mpu (min packet unit) is also encoded into the old rate table, thus
380	* starting from the mpu, we find low and high table entries for
381	* mapping this cell. If these entries contain the same value, when
382	* the rate tables have been modified for linklayer ATM.
383	*
384	* This is done by rounding mpu to the nearest 48 bytes cell/entry,
385	* and then roundup to the next cell, calc the table entry one below,
386	* and compare.
387	*/
388	static __u8 __detect_linklayer(struct tc_ratespec *r, __u32 *rtab)
389	{
390	int low = roundup(r->mpu, 48);
391	int high = roundup(low+1, 48);
392	int cell_low = low >> r->cell_log;
393	int cell_high = (high >> r->cell_log) - 1;
394
395	/* rtab is too inaccurate at rates > 100Mbit/s */
396	if ((r->rate > (100000000/8)) || (rtab[0] == 0)) {
397	pr_debug("TC linklayer: Giving up ATM detection\n");
398	return TC_LINKLAYER_ETHERNET;
399	}
400
401	if ((cell_high > cell_low) && (cell_high < 256)
402	&& (rtab[cell_low] == rtab[cell_high])) {
403	pr_debug("TC linklayer: Detected ATM, low(%d)=high(%d)=%u\n",
404	cell_low, cell_high, rtab[cell_high]);
405	return TC_LINKLAYER_ATM;
406	}
407	return TC_LINKLAYER_ETHERNET;
408	}
409
410	static struct qdisc_rate_table *qdisc_rtab_list;
411
412	struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r,
413	struct nlattr *tab,
414	struct netlink_ext_ack *extack)
415	{
416	struct qdisc_rate_table *rtab;
417
418	if (tab == NULL || r->rate == 0 ||
419	r->cell_log == 0 || r->cell_log >= 32 ||
420	nla_len(nla: tab) != TC_RTAB_SIZE) {
421	NL_SET_ERR_MSG(extack, "Invalid rate table parameters for searching");
422	return NULL;
423	}
424
425	for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) {
426	if (!memcmp(p: &rtab->rate, q: r, size: sizeof(struct tc_ratespec)) &&
427	!memcmp(p: &rtab->data, q: nla_data(nla: tab), size: 1024)) {
428	rtab->refcnt++;
429	return rtab;
430	}
431	}
432
433	rtab = kmalloc(size: sizeof(*rtab), GFP_KERNEL);
434	if (rtab) {
435	rtab->rate = *r;
436	rtab->refcnt = 1;
437	memcpy(rtab->data, nla_data(tab), 1024);
438	if (r->linklayer == TC_LINKLAYER_UNAWARE)
439	r->linklayer = __detect_linklayer(r, rtab: rtab->data);
440	rtab->next = qdisc_rtab_list;
441	qdisc_rtab_list = rtab;
442	} else {
443	NL_SET_ERR_MSG(extack, "Failed to allocate new qdisc rate table");
444	}
445	return rtab;
446	}
447	EXPORT_SYMBOL(qdisc_get_rtab);
448
449	void qdisc_put_rtab(struct qdisc_rate_table *tab)
450	{
451	struct qdisc_rate_table *rtab, **rtabp;
452
453	if (!tab || --tab->refcnt)
454	return;
455
456	for (rtabp = &qdisc_rtab_list;
457	(rtab = *rtabp) != NULL;
458	rtabp = &rtab->next) {
459	if (rtab == tab) {
460	*rtabp = rtab->next;
461	kfree(objp: rtab);
462	return;
463	}
464	}
465	}
466	EXPORT_SYMBOL(qdisc_put_rtab);
467
468	static LIST_HEAD(qdisc_stab_list);
469
470	static const struct nla_policy stab_policy[TCA_STAB_MAX + 1] = {
471	[TCA_STAB_BASE] = { .len = sizeof(struct tc_sizespec) },
472	[TCA_STAB_DATA] = { .type = NLA_BINARY },
473	};
474
475	static struct qdisc_size_table *qdisc_get_stab(struct nlattr *opt,
476	struct netlink_ext_ack *extack)
477	{
478	struct nlattr *tb[TCA_STAB_MAX + 1];
479	struct qdisc_size_table *stab;
480	struct tc_sizespec *s;
481	unsigned int tsize = 0;
482	u16 *tab = NULL;
483	int err;
484
485	err = nla_parse_nested_deprecated(tb, TCA_STAB_MAX, nla: opt, policy: stab_policy,
486	extack);
487	if (err < 0)
488	return ERR_PTR(error: err);
489	if (!tb[TCA_STAB_BASE]) {
490	NL_SET_ERR_MSG(extack, "Size table base attribute is missing");
491	return ERR_PTR(error: -EINVAL);
492	}
493
494	s = nla_data(nla: tb[TCA_STAB_BASE]);
495
496	if (s->tsize > 0) {
497	if (!tb[TCA_STAB_DATA]) {
498	NL_SET_ERR_MSG(extack, "Size table data attribute is missing");
499	return ERR_PTR(error: -EINVAL);
500	}
501	tab = nla_data(nla: tb[TCA_STAB_DATA]);
502	tsize = nla_len(nla: tb[TCA_STAB_DATA]) / sizeof(u16);
503	}
504
505	if (tsize != s->tsize || (!tab && tsize > 0)) {
506	NL_SET_ERR_MSG(extack, "Invalid size of size table");
507	return ERR_PTR(error: -EINVAL);
508	}
509
510	list_for_each_entry(stab, &qdisc_stab_list, list) {
511	if (memcmp(p: &stab->szopts, q: s, size: sizeof(*s)))
512	continue;
513	if (tsize > 0 &&
514	memcmp(p: stab->data, q: tab, flex_array_size(stab, data, tsize)))
515	continue;
516	stab->refcnt++;
517	return stab;
518	}
519
520	if (s->size_log > STAB_SIZE_LOG_MAX ||
521	s->cell_log > STAB_SIZE_LOG_MAX) {
522	NL_SET_ERR_MSG(extack, "Invalid logarithmic size of size table");
523	return ERR_PTR(error: -EINVAL);
524	}
525
526	stab = kmalloc(struct_size(stab, data, tsize), GFP_KERNEL);
527	if (!stab)
528	return ERR_PTR(error: -ENOMEM);
529
530	stab->refcnt = 1;
531	stab->szopts = *s;
532	if (tsize > 0)
533	memcpy(stab->data, tab, flex_array_size(stab, data, tsize));
534
535	list_add_tail(new: &stab->list, head: &qdisc_stab_list);
536
537	return stab;
538	}
539
540	void qdisc_put_stab(struct qdisc_size_table *tab)
541	{
542	if (!tab)
543	return;
544
545	if (--tab->refcnt == 0) {
546	list_del(entry: &tab->list);
547	kfree_rcu(tab, rcu);
548	}
549	}
550	EXPORT_SYMBOL(qdisc_put_stab);
551
552	static int qdisc_dump_stab(struct sk_buff *skb, struct qdisc_size_table *stab)
553	{
554	struct nlattr *nest;
555
556	nest = nla_nest_start_noflag(skb, attrtype: TCA_STAB);
557	if (nest == NULL)
558	goto nla_put_failure;
559	if (nla_put(skb, attrtype: TCA_STAB_BASE, attrlen: sizeof(stab->szopts), data: &stab->szopts))
560	goto nla_put_failure;
561	nla_nest_end(skb, start: nest);
562
563	return skb->len;
564
565	nla_put_failure:
566	return -1;
567	}
568
569	void __qdisc_calculate_pkt_len(struct sk_buff *skb,
570	const struct qdisc_size_table *stab)
571	{
572	int pkt_len, slot;
573
574	pkt_len = skb->len + stab->szopts.overhead;
575	if (unlikely(!stab->szopts.tsize))
576	goto out;
577
578	slot = pkt_len + stab->szopts.cell_align;
579	if (unlikely(slot < 0))
580	slot = 0;
581
582	slot >>= stab->szopts.cell_log;
583	if (likely(slot < stab->szopts.tsize))
584	pkt_len = stab->data[slot];
585	else
586	pkt_len = stab->data[stab->szopts.tsize - 1] *
587	(slot / stab->szopts.tsize) +
588	stab->data[slot % stab->szopts.tsize];
589
590	pkt_len <<= stab->szopts.size_log;
591	out:
592	if (unlikely(pkt_len < 1))
593	pkt_len = 1;
594	qdisc_skb_cb(skb)->pkt_len = pkt_len;
595	}
596	EXPORT_SYMBOL(__qdisc_calculate_pkt_len);
597
598	void qdisc_warn_nonwc(const char *txt, struct Qdisc *qdisc)
599	{
600	if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
601	pr_warn("%s: %s qdisc %X: is non-work-conserving?\n",
602	txt, qdisc->ops->id, qdisc->handle >> 16);
603	qdisc->flags |= TCQ_F_WARN_NONWC;
604	}
605	}
606	EXPORT_SYMBOL(qdisc_warn_nonwc);
607
608	static enum hrtimer_restart qdisc_watchdog(struct hrtimer *timer)
609	{
610	struct qdisc_watchdog *wd = container_of(timer, struct qdisc_watchdog,
611	timer);
612
613	rcu_read_lock();
614	__netif_schedule(q: qdisc_root(qdisc: wd->qdisc));
615	rcu_read_unlock();
616
617	return HRTIMER_NORESTART;
618	}
619
620	void qdisc_watchdog_init_clockid(struct qdisc_watchdog *wd, struct Qdisc *qdisc,
621	clockid_t clockid)
622	{
623	hrtimer_init(timer: &wd->timer, which_clock: clockid, mode: HRTIMER_MODE_ABS_PINNED);
624	wd->timer.function = qdisc_watchdog;
625	wd->qdisc = qdisc;
626	}
627	EXPORT_SYMBOL(qdisc_watchdog_init_clockid);
628
629	void qdisc_watchdog_init(struct qdisc_watchdog *wd, struct Qdisc *qdisc)
630	{
631	qdisc_watchdog_init_clockid(wd, qdisc, CLOCK_MONOTONIC);
632	}
633	EXPORT_SYMBOL(qdisc_watchdog_init);
634
635	void qdisc_watchdog_schedule_range_ns(struct qdisc_watchdog *wd, u64 expires,
636	u64 delta_ns)
637	{
638	bool deactivated;
639
640	rcu_read_lock();
641	deactivated = test_bit(__QDISC_STATE_DEACTIVATED,
642	&qdisc_root_sleeping(wd->qdisc)->state);
643	rcu_read_unlock();
644	if (deactivated)
645	return;
646
647	if (hrtimer_is_queued(timer: &wd->timer)) {
648	u64 softexpires;
649
650	softexpires = ktime_to_ns(kt: hrtimer_get_softexpires(timer: &wd->timer));
651	/* If timer is already set in [expires, expires + delta_ns],
652	* do not reprogram it.
653	*/
654	if (softexpires - expires <= delta_ns)
655	return;
656	}
657
658	hrtimer_start_range_ns(timer: &wd->timer,
659	tim: ns_to_ktime(ns: expires),
660	range_ns: delta_ns,
661	mode: HRTIMER_MODE_ABS_PINNED);
662	}
663	EXPORT_SYMBOL(qdisc_watchdog_schedule_range_ns);
664
665	void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
666	{
667	hrtimer_cancel(timer: &wd->timer);
668	}
669	EXPORT_SYMBOL(qdisc_watchdog_cancel);
670
671	static struct hlist_head *qdisc_class_hash_alloc(unsigned int n)
672	{
673	struct hlist_head *h;
674	unsigned int i;
675
676	h = kvmalloc_array(n, size: sizeof(struct hlist_head), GFP_KERNEL);
677
678	if (h != NULL) {
679	for (i = 0; i < n; i++)
680	INIT_HLIST_HEAD(&h[i]);
681	}
682	return h;
683	}
684
685	void qdisc_class_hash_grow(struct Qdisc *sch, struct Qdisc_class_hash *clhash)
686	{
687	struct Qdisc_class_common *cl;
688	struct hlist_node *next;
689	struct hlist_head *nhash, *ohash;
690	unsigned int nsize, nmask, osize;
691	unsigned int i, h;
692
693	/* Rehash when load factor exceeds 0.75 */
694	if (clhash->hashelems * 4 <= clhash->hashsize * 3)
695	return;
696	nsize = clhash->hashsize * 2;
697	nmask = nsize - 1;
698	nhash = qdisc_class_hash_alloc(n: nsize);
699	if (nhash == NULL)
700	return;
701
702	ohash = clhash->hash;
703	osize = clhash->hashsize;
704
705	sch_tree_lock(q: sch);
706	for (i = 0; i < osize; i++) {
707	hlist_for_each_entry_safe(cl, next, &ohash[i], hnode) {
708	h = qdisc_class_hash(id: cl->classid, mask: nmask);
709	hlist_add_head(n: &cl->hnode, h: &nhash[h]);
710	}
711	}
712	clhash->hash = nhash;
713	clhash->hashsize = nsize;
714	clhash->hashmask = nmask;
715	sch_tree_unlock(q: sch);
716
717	kvfree(addr: ohash);
718	}
719	EXPORT_SYMBOL(qdisc_class_hash_grow);
720
721	int qdisc_class_hash_init(struct Qdisc_class_hash *clhash)
722	{
723	unsigned int size = 4;
724
725	clhash->hash = qdisc_class_hash_alloc(n: size);
726	if (!clhash->hash)
727	return -ENOMEM;
728	clhash->hashsize = size;
729	clhash->hashmask = size - 1;
730	clhash->hashelems = 0;
731	return 0;
732	}
733	EXPORT_SYMBOL(qdisc_class_hash_init);
734
735	void qdisc_class_hash_destroy(struct Qdisc_class_hash *clhash)
736	{
737	kvfree(addr: clhash->hash);
738	}
739	EXPORT_SYMBOL(qdisc_class_hash_destroy);
740
741	void qdisc_class_hash_insert(struct Qdisc_class_hash *clhash,
742	struct Qdisc_class_common *cl)
743	{
744	unsigned int h;
745
746	INIT_HLIST_NODE(h: &cl->hnode);
747	h = qdisc_class_hash(id: cl->classid, mask: clhash->hashmask);
748	hlist_add_head(n: &cl->hnode, h: &clhash->hash[h]);
749	clhash->hashelems++;
750	}
751	EXPORT_SYMBOL(qdisc_class_hash_insert);
752
753	void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
754	struct Qdisc_class_common *cl)
755	{
756	hlist_del(n: &cl->hnode);
757	clhash->hashelems--;
758	}
759	EXPORT_SYMBOL(qdisc_class_hash_remove);
760
761	/* Allocate an unique handle from space managed by kernel
762	* Possible range is [8000-FFFF]:0000 (0x8000 values)
763	*/
764	static u32 qdisc_alloc_handle(struct net_device *dev)
765	{
766	int i = 0x8000;
767	static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
768
769	do {
770	autohandle += TC_H_MAKE(0x10000U, 0);
771	if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
772	autohandle = TC_H_MAKE(0x80000000U, 0);
773	if (!qdisc_lookup(dev, handle: autohandle))
774	return autohandle;
775	cond_resched();
776	} while (--i > 0);
777
778	return 0;
779	}
780
781	void qdisc_tree_reduce_backlog(struct Qdisc *sch, int n, int len)
782	{
783	bool qdisc_is_offloaded = sch->flags & TCQ_F_OFFLOADED;
784	const struct Qdisc_class_ops *cops;
785	unsigned long cl;
786	u32 parentid;
787	bool notify;
788	int drops;
789
790	if (n == 0 && len == 0)
791	return;
792	drops = max_t(int, n, 0);
793	rcu_read_lock();
794	while ((parentid = sch->parent)) {
795	if (TC_H_MAJ(parentid) == TC_H_MAJ(TC_H_INGRESS))
796	break;
797
798	if (sch->flags & TCQ_F_NOPARENT)
799	break;
800	/* Notify parent qdisc only if child qdisc becomes empty.
801	*
802	* If child was empty even before update then backlog
803	* counter is screwed and we skip notification because
804	* parent class is already passive.
805	*
806	* If the original child was offloaded then it is allowed
807	* to be seem as empty, so the parent is notified anyway.
808	*/
809	notify = !sch->q.qlen && !WARN_ON_ONCE(!n &&
810	!qdisc_is_offloaded);
811	/* TODO: perform the search on a per txq basis */
812	sch = qdisc_lookup(dev: qdisc_dev(qdisc: sch), TC_H_MAJ(parentid));
813	if (sch == NULL) {
814	WARN_ON_ONCE(parentid != TC_H_ROOT);
815	break;
816	}
817	cops = sch->ops->cl_ops;
818	if (notify && cops->qlen_notify) {
819	cl = cops->find(sch, parentid);
820	cops->qlen_notify(sch, cl);
821	}
822	sch->q.qlen -= n;
823	sch->qstats.backlog -= len;
824	__qdisc_qstats_drop(sch, count: drops);
825	}
826	rcu_read_unlock();
827	}
828	EXPORT_SYMBOL(qdisc_tree_reduce_backlog);
829
830	int qdisc_offload_dump_helper(struct Qdisc *sch, enum tc_setup_type type,
831	void *type_data)
832	{
833	struct net_device *dev = qdisc_dev(qdisc: sch);
834	int err;
835
836	sch->flags &= ~TCQ_F_OFFLOADED;
837	if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
838	return 0;
839
840	err = dev->netdev_ops->ndo_setup_tc(dev, type, type_data);
841	if (err == -EOPNOTSUPP)
842	return 0;
843
844	if (!err)
845	sch->flags |= TCQ_F_OFFLOADED;
846
847	return err;
848	}
849	EXPORT_SYMBOL(qdisc_offload_dump_helper);
850
851	void qdisc_offload_graft_helper(struct net_device *dev, struct Qdisc *sch,
852	struct Qdisc *new, struct Qdisc *old,
853	enum tc_setup_type type, void *type_data,
854	struct netlink_ext_ack *extack)
855	{
856	bool any_qdisc_is_offloaded;
857	int err;
858
859	if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
860	return;
861
862	err = dev->netdev_ops->ndo_setup_tc(dev, type, type_data);
863
864	/* Don't report error if the graft is part of destroy operation. */
865	if (!err || !new || new == &noop_qdisc)
866	return;
867
868	/* Don't report error if the parent, the old child and the new
869	* one are not offloaded.
870	*/
871	any_qdisc_is_offloaded = new->flags & TCQ_F_OFFLOADED;
872	any_qdisc_is_offloaded |= sch && sch->flags & TCQ_F_OFFLOADED;
873	any_qdisc_is_offloaded |= old && old->flags & TCQ_F_OFFLOADED;
874
875	if (any_qdisc_is_offloaded)
876	NL_SET_ERR_MSG(extack, "Offloading graft operation failed.");
877	}
878	EXPORT_SYMBOL(qdisc_offload_graft_helper);
879
880	void qdisc_offload_query_caps(struct net_device *dev,
881	enum tc_setup_type type,
882	void *caps, size_t caps_len)
883	{
884	const struct net_device_ops *ops = dev->netdev_ops;
885	struct tc_query_caps_base base = {
886	.type = type,
887	.caps = caps,
888	};
889
890	memset(caps, 0, caps_len);
891
892	if (ops->ndo_setup_tc)
893	ops->ndo_setup_tc(dev, TC_QUERY_CAPS, &base);
894	}
895	EXPORT_SYMBOL(qdisc_offload_query_caps);
896
897	static void qdisc_offload_graft_root(struct net_device *dev,
898	struct Qdisc *new, struct Qdisc *old,
899	struct netlink_ext_ack *extack)
900	{
901	struct tc_root_qopt_offload graft_offload = {
902	.command = TC_ROOT_GRAFT,
903	.handle = new ? new->handle : 0,
904	.ingress = (new && new->flags & TCQ_F_INGRESS) ||
905	(old && old->flags & TCQ_F_INGRESS),
906	};
907
908	qdisc_offload_graft_helper(dev, NULL, new, old,
909	TC_SETUP_ROOT_QDISC, &graft_offload, extack);
910	}
911
912	static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
913	u32 portid, u32 seq, u16 flags, int event,
914	struct netlink_ext_ack *extack)
915	{
916	struct gnet_stats_basic_sync __percpu *cpu_bstats = NULL;
917	struct gnet_stats_queue __percpu *cpu_qstats = NULL;
918	struct tcmsg *tcm;
919	struct nlmsghdr *nlh;
920	unsigned char *b = skb_tail_pointer(skb);
921	struct gnet_dump d;
922	struct qdisc_size_table *stab;
923	u32 block_index;
924	__u32 qlen;
925
926	cond_resched();
927	nlh = nlmsg_put(skb, portid, seq, type: event, payload: sizeof(*tcm), flags);
928	if (!nlh)
929	goto out_nlmsg_trim;
930	tcm = nlmsg_data(nlh);
931	tcm->tcm_family = AF_UNSPEC;
932	tcm->tcm__pad1 = 0;
933	tcm->tcm__pad2 = 0;
934	tcm->tcm_ifindex = qdisc_dev(qdisc: q)->ifindex;
935	tcm->tcm_parent = clid;
936	tcm->tcm_handle = q->handle;
937	tcm->tcm_info = refcount_read(r: &q->refcnt);
938	if (nla_put_string(skb, attrtype: TCA_KIND, str: q->ops->id))
939	goto nla_put_failure;
940	if (q->ops->ingress_block_get) {
941	block_index = q->ops->ingress_block_get(q);
942	if (block_index &&
943	nla_put_u32(skb, attrtype: TCA_INGRESS_BLOCK, value: block_index))
944	goto nla_put_failure;
945	}
946	if (q->ops->egress_block_get) {
947	block_index = q->ops->egress_block_get(q);
948	if (block_index &&
949	nla_put_u32(skb, attrtype: TCA_EGRESS_BLOCK, value: block_index))
950	goto nla_put_failure;
951	}
952	if (q->ops->dump && q->ops->dump(q, skb) < 0)
953	goto nla_put_failure;
954	if (nla_put_u8(skb, attrtype: TCA_HW_OFFLOAD, value: !!(q->flags & TCQ_F_OFFLOADED)))
955	goto nla_put_failure;
956	qlen = qdisc_qlen_sum(q);
957
958	stab = rtnl_dereference(q->stab);
959	if (stab && qdisc_dump_stab(skb, stab) < 0)
960	goto nla_put_failure;
961
962	if (gnet_stats_start_copy_compat(skb, type: TCA_STATS2, tc_stats_type: TCA_STATS, xstats_type: TCA_XSTATS,
963	NULL, d: &d, padattr: TCA_PAD) < 0)
964	goto nla_put_failure;
965
966	if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
967	goto nla_put_failure;
968
969	if (qdisc_is_percpu_stats(q)) {
970	cpu_bstats = q->cpu_bstats;
971	cpu_qstats = q->cpu_qstats;
972	}
973
974	if (gnet_stats_copy_basic(d: &d, cpu: cpu_bstats, b: &q->bstats, running: true) < 0 ||
975	gnet_stats_copy_rate_est(d: &d, ptr: &q->rate_est) < 0 ||
976	gnet_stats_copy_queue(d: &d, cpu_q: cpu_qstats, q: &q->qstats, qlen) < 0)
977	goto nla_put_failure;
978
979	if (gnet_stats_finish_copy(d: &d) < 0)
980	goto nla_put_failure;
981
982	if (extack && extack->_msg &&
983	nla_put_string(skb, attrtype: TCA_EXT_WARN_MSG, str: extack->_msg))
984	goto out_nlmsg_trim;
985
986	nlh->nlmsg_len = skb_tail_pointer(skb) - b;
987
988	return skb->len;
989
990	out_nlmsg_trim:
991	nla_put_failure:
992	nlmsg_trim(skb, mark: b);
993	return -1;
994	}
995
996	static bool tc_qdisc_dump_ignore(struct Qdisc *q, bool dump_invisible)
997	{
998	if (q->flags & TCQ_F_BUILTIN)
999	return true;
1000	if ((q->flags & TCQ_F_INVISIBLE) && !dump_invisible)
1001	return true;
1002
1003	return false;
1004	}
1005
1006	static int qdisc_notify(struct net *net, struct sk_buff *oskb,
1007	struct nlmsghdr *n, u32 clid,
1008	struct Qdisc *old, struct Qdisc *new,
1009	struct netlink_ext_ack *extack)
1010	{
1011	struct sk_buff *skb;
1012	u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
1013
1014	skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1015	if (!skb)
1016	return -ENOBUFS;
1017
1018	if (old && !tc_qdisc_dump_ignore(q: old, dump_invisible: false)) {
1019	if (tc_fill_qdisc(skb, q: old, clid, portid, seq: n->nlmsg_seq,
1020	flags: 0, RTM_DELQDISC, extack) < 0)
1021	goto err_out;
1022	}
1023	if (new && !tc_qdisc_dump_ignore(q: new, dump_invisible: false)) {
1024	if (tc_fill_qdisc(skb, q: new, clid, portid, seq: n->nlmsg_seq,
1025	flags: old ? NLM_F_REPLACE : 0, RTM_NEWQDISC, extack) < 0)
1026	goto err_out;
1027	}
1028
1029	if (skb->len)
1030	return rtnetlink_send(skb, net, pid: portid, RTNLGRP_TC,
1031	echo: n->nlmsg_flags & NLM_F_ECHO);
1032
1033	err_out:
1034	kfree_skb(skb);
1035	return -EINVAL;
1036	}
1037
1038	static void notify_and_destroy(struct net *net, struct sk_buff *skb,
1039	struct nlmsghdr *n, u32 clid,
1040	struct Qdisc *old, struct Qdisc *new,
1041	struct netlink_ext_ack *extack)
1042	{
1043	if (new || old)
1044	qdisc_notify(net, oskb: skb, n, clid, old, new, extack);
1045
1046	if (old)
1047	qdisc_put(qdisc: old);
1048	}
1049
1050	static void qdisc_clear_nolock(struct Qdisc *sch)
1051	{
1052	sch->flags &= ~TCQ_F_NOLOCK;
1053	if (!(sch->flags & TCQ_F_CPUSTATS))
1054	return;
1055
1056	free_percpu(pdata: sch->cpu_bstats);
1057	free_percpu(pdata: sch->cpu_qstats);
1058	sch->cpu_bstats = NULL;
1059	sch->cpu_qstats = NULL;
1060	sch->flags &= ~TCQ_F_CPUSTATS;
1061	}
1062
1063	/* Graft qdisc "new" to class "classid" of qdisc "parent" or
1064	* to device "dev".
1065	*
1066	* When appropriate send a netlink notification using 'skb'
1067	* and "n".
1068	*
1069	* On success, destroy old qdisc.
1070	*/
1071
1072	static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
1073	struct sk_buff *skb, struct nlmsghdr *n, u32 classid,
1074	struct Qdisc *new, struct Qdisc *old,
1075	struct netlink_ext_ack *extack)
1076	{
1077	struct Qdisc *q = old;
1078	struct net *net = dev_net(dev);
1079
1080	if (parent == NULL) {
1081	unsigned int i, num_q, ingress;
1082	struct netdev_queue *dev_queue;
1083
1084	ingress = 0;
1085	num_q = dev->num_tx_queues;
1086	if ((q && q->flags & TCQ_F_INGRESS) ||
1087	(new && new->flags & TCQ_F_INGRESS)) {
1088	ingress = 1;
1089	dev_queue = dev_ingress_queue(dev);
1090	if (!dev_queue) {
1091	NL_SET_ERR_MSG(extack, "Device does not have an ingress queue");
1092	return -ENOENT;
1093	}
1094
1095	q = rtnl_dereference(dev_queue->qdisc_sleeping);
1096
1097	/* This is the counterpart of that qdisc_refcount_inc_nz() call in
1098	* __tcf_qdisc_find() for filter requests.
1099	*/
1100	if (!qdisc_refcount_dec_if_one(qdisc: q)) {
1101	NL_SET_ERR_MSG(extack,
1102	"Current ingress or clsact Qdisc has ongoing filter requests");
1103	return -EBUSY;
1104	}
1105	}
1106
1107	if (dev->flags & IFF_UP)
1108	dev_deactivate(dev);
1109
1110	qdisc_offload_graft_root(dev, new, old, extack);
1111
1112	if (new && new->ops->attach && !ingress)
1113	goto skip;
1114
1115	if (!ingress) {
1116	for (i = 0; i < num_q; i++) {
1117	dev_queue = netdev_get_tx_queue(dev, index: i);
1118	old = dev_graft_qdisc(dev_queue, qdisc: new);
1119
1120	if (new && i > 0)
1121	qdisc_refcount_inc(qdisc: new);
1122	qdisc_put(qdisc: old);
1123	}
1124	} else {
1125	old = dev_graft_qdisc(dev_queue, NULL);
1126
1127	/* {ingress,clsact}_destroy() @old before grafting @new to avoid
1128	* unprotected concurrent accesses to net_device::miniq_{in,e}gress
1129	* pointer(s) in mini_qdisc_pair_swap().
1130	*/
1131	qdisc_notify(net, oskb: skb, n, clid: classid, old, new, extack);
1132	qdisc_destroy(qdisc: old);
1133
1134	dev_graft_qdisc(dev_queue, qdisc: new);
1135	}
1136
1137	skip:
1138	if (!ingress) {
1139	old = rtnl_dereference(dev->qdisc);
1140	if (new && !new->ops->attach)
1141	qdisc_refcount_inc(qdisc: new);
1142	rcu_assign_pointer(dev->qdisc, new ? : &noop_qdisc);
1143
1144	notify_and_destroy(net, skb, n, clid: classid, old, new, extack);
1145
1146	if (new && new->ops->attach)
1147	new->ops->attach(new);
1148	}
1149
1150	if (dev->flags & IFF_UP)
1151	dev_activate(dev);
1152	} else {
1153	const struct Qdisc_class_ops *cops = parent->ops->cl_ops;
1154	unsigned long cl;
1155	int err;
1156
1157	/* Only support running class lockless if parent is lockless */
1158	if (new && (new->flags & TCQ_F_NOLOCK) && !(parent->flags & TCQ_F_NOLOCK))
1159	qdisc_clear_nolock(sch: new);
1160
1161	if (!cops || !cops->graft)
1162	return -EOPNOTSUPP;
1163
1164	cl = cops->find(parent, classid);
1165	if (!cl) {
1166	NL_SET_ERR_MSG(extack, "Specified class not found");
1167	return -ENOENT;
1168	}
1169
1170	if (new && new->ops == &noqueue_qdisc_ops) {
1171	NL_SET_ERR_MSG(extack, "Cannot assign noqueue to a class");
1172	return -EINVAL;
1173	}
1174
1175	err = cops->graft(parent, cl, new, &old, extack);
1176	if (err)
1177	return err;
1178	notify_and_destroy(net, skb, n, clid: classid, old, new, extack);
1179	}
1180	return 0;
1181	}
1182
1183	static int qdisc_block_indexes_set(struct Qdisc *sch, struct nlattr **tca,
1184	struct netlink_ext_ack *extack)
1185	{
1186	u32 block_index;
1187
1188	if (tca[TCA_INGRESS_BLOCK]) {
1189	block_index = nla_get_u32(nla: tca[TCA_INGRESS_BLOCK]);
1190
1191	if (!block_index) {
1192	NL_SET_ERR_MSG(extack, "Ingress block index cannot be 0");
1193	return -EINVAL;
1194	}
1195	if (!sch->ops->ingress_block_set) {
1196	NL_SET_ERR_MSG(extack, "Ingress block sharing is not supported");
1197	return -EOPNOTSUPP;
1198	}
1199	sch->ops->ingress_block_set(sch, block_index);
1200	}
1201	if (tca[TCA_EGRESS_BLOCK]) {
1202	block_index = nla_get_u32(nla: tca[TCA_EGRESS_BLOCK]);
1203
1204	if (!block_index) {
1205	NL_SET_ERR_MSG(extack, "Egress block index cannot be 0");
1206	return -EINVAL;
1207	}
1208	if (!sch->ops->egress_block_set) {
1209	NL_SET_ERR_MSG(extack, "Egress block sharing is not supported");
1210	return -EOPNOTSUPP;
1211	}
1212	sch->ops->egress_block_set(sch, block_index);
1213	}
1214	return 0;
1215	}
1216
1217	/*
1218	Allocate and initialize new qdisc.
1219
1220	Parameters are passed via opt.
1221	*/
1222
1223	static struct Qdisc *qdisc_create(struct net_device *dev,
1224	struct netdev_queue *dev_queue,
1225	u32 parent, u32 handle,
1226	struct nlattr **tca, int *errp,
1227	struct netlink_ext_ack *extack)
1228	{
1229	int err;
1230	struct nlattr *kind = tca[TCA_KIND];
1231	struct Qdisc *sch;
1232	struct Qdisc_ops *ops;
1233	struct qdisc_size_table *stab;
1234
1235	ops = qdisc_lookup_ops(kind);
1236	#ifdef CONFIG_MODULES
1237	if (ops == NULL && kind != NULL) {
1238	char name[IFNAMSIZ];
1239	if (nla_strscpy(dst: name, nla: kind, IFNAMSIZ) >= 0) {
1240	/* We dropped the RTNL semaphore in order to
1241	* perform the module load. So, even if we
1242	* succeeded in loading the module we have to
1243	* tell the caller to replay the request. We
1244	* indicate this using -EAGAIN.
1245	* We replay the request because the device may
1246	* go away in the mean time.
1247	*/
1248	rtnl_unlock();
1249	request_module("sch_%s", name);
1250	rtnl_lock();
1251	ops = qdisc_lookup_ops(kind);
1252	if (ops != NULL) {
1253	/* We will try again qdisc_lookup_ops,
1254	* so don't keep a reference.
1255	*/
1256	module_put(module: ops->owner);
1257	err = -EAGAIN;
1258	goto err_out;
1259	}
1260	}
1261	}
1262	#endif
1263
1264	err = -ENOENT;
1265	if (!ops) {
1266	NL_SET_ERR_MSG(extack, "Specified qdisc kind is unknown");
1267	goto err_out;
1268	}
1269
1270	sch = qdisc_alloc(dev_queue, ops, extack);
1271	if (IS_ERR(ptr: sch)) {
1272	err = PTR_ERR(ptr: sch);
1273	goto err_out2;
1274	}
1275
1276	sch->parent = parent;
1277
1278	if (handle == TC_H_INGRESS) {
1279	if (!(sch->flags & TCQ_F_INGRESS)) {
1280	NL_SET_ERR_MSG(extack,
1281	"Specified parent ID is reserved for ingress and clsact Qdiscs");
1282	err = -EINVAL;
1283	goto err_out3;
1284	}
1285	handle = TC_H_MAKE(TC_H_INGRESS, 0);
1286	} else {
1287	if (handle == 0) {
1288	handle = qdisc_alloc_handle(dev);
1289	if (handle == 0) {
1290	NL_SET_ERR_MSG(extack, "Maximum number of qdisc handles was exceeded");
1291	err = -ENOSPC;
1292	goto err_out3;
1293	}
1294	}
1295	if (!netif_is_multiqueue(dev))
1296	sch->flags |= TCQ_F_ONETXQUEUE;
1297	}
1298
1299	sch->handle = handle;
1300
1301	/* This exist to keep backward compatible with a userspace
1302	* loophole, what allowed userspace to get IFF_NO_QUEUE
1303	* facility on older kernels by setting tx_queue_len=0 (prior
1304	* to qdisc init), and then forgot to reinit tx_queue_len
1305	* before again attaching a qdisc.
1306	*/
1307	if ((dev->priv_flags & IFF_NO_QUEUE) && (dev->tx_queue_len == 0)) {
1308	dev->tx_queue_len = DEFAULT_TX_QUEUE_LEN;
1309	netdev_info(dev, format: "Caught tx_queue_len zero misconfig\n");
1310	}
1311
1312	err = qdisc_block_indexes_set(sch, tca, extack);
1313	if (err)
1314	goto err_out3;
1315
1316	if (tca[TCA_STAB]) {
1317	stab = qdisc_get_stab(opt: tca[TCA_STAB], extack);
1318	if (IS_ERR(ptr: stab)) {
1319	err = PTR_ERR(ptr: stab);
1320	goto err_out3;
1321	}
1322	rcu_assign_pointer(sch->stab, stab);
1323	}
1324
1325	if (ops->init) {
1326	err = ops->init(sch, tca[TCA_OPTIONS], extack);
1327	if (err != 0)
1328	goto err_out4;
1329	}
1330
1331	if (tca[TCA_RATE]) {
1332	err = -EOPNOTSUPP;
1333	if (sch->flags & TCQ_F_MQROOT) {
1334	NL_SET_ERR_MSG(extack, "Cannot attach rate estimator to a multi-queue root qdisc");
1335	goto err_out4;
1336	}
1337
1338	err = gen_new_estimator(bstats: &sch->bstats,
1339	cpu_bstats: sch->cpu_bstats,
1340	rate_est: &sch->rate_est,
1341	NULL,
1342	running: true,
1343	opt: tca[TCA_RATE]);
1344	if (err) {
1345	NL_SET_ERR_MSG(extack, "Failed to generate new estimator");
1346	goto err_out4;
1347	}
1348	}
1349
1350	qdisc_hash_add(sch, false);
1351	trace_qdisc_create(ops, dev, parent);
1352
1353	return sch;
1354
1355	err_out4:
1356	/* Even if ops->init() failed, we call ops->destroy()
1357	* like qdisc_create_dflt().
1358	*/
1359	if (ops->destroy)
1360	ops->destroy(sch);
1361	qdisc_put_stab(rtnl_dereference(sch->stab));
1362	err_out3:
1363	netdev_put(dev, tracker: &sch->dev_tracker);
1364	qdisc_free(qdisc: sch);
1365	err_out2:
1366	module_put(module: ops->owner);
1367	err_out:
1368	*errp = err;
1369	return NULL;
1370	}
1371
1372	static int qdisc_change(struct Qdisc *sch, struct nlattr **tca,
1373	struct netlink_ext_ack *extack)
1374	{
1375	struct qdisc_size_table *ostab, *stab = NULL;
1376	int err = 0;
1377
1378	if (tca[TCA_OPTIONS]) {
1379	if (!sch->ops->change) {
1380	NL_SET_ERR_MSG(extack, "Change operation not supported by specified qdisc");
1381	return -EINVAL;
1382	}
1383	if (tca[TCA_INGRESS_BLOCK] || tca[TCA_EGRESS_BLOCK]) {
1384	NL_SET_ERR_MSG(extack, "Change of blocks is not supported");
1385	return -EOPNOTSUPP;
1386	}
1387	err = sch->ops->change(sch, tca[TCA_OPTIONS], extack);
1388	if (err)
1389	return err;
1390	}
1391
1392	if (tca[TCA_STAB]) {
1393	stab = qdisc_get_stab(opt: tca[TCA_STAB], extack);
1394	if (IS_ERR(ptr: stab))
1395	return PTR_ERR(ptr: stab);
1396	}
1397
1398	ostab = rtnl_dereference(sch->stab);
1399	rcu_assign_pointer(sch->stab, stab);
1400	qdisc_put_stab(ostab);
1401
1402	if (tca[TCA_RATE]) {
1403	/* NB: ignores errors from replace_estimator
1404	because change can't be undone. */
1405	if (sch->flags & TCQ_F_MQROOT)
1406	goto out;
1407	gen_replace_estimator(bstats: &sch->bstats,
1408	cpu_bstats: sch->cpu_bstats,
1409	ptr: &sch->rate_est,
1410	NULL,
1411	running: true,
1412	opt: tca[TCA_RATE]);
1413	}
1414	out:
1415	return 0;
1416	}
1417
1418	struct check_loop_arg {
1419	struct qdisc_walker w;
1420	struct Qdisc *p;
1421	int depth;
1422	};
1423
1424	static int check_loop_fn(struct Qdisc *q, unsigned long cl,
1425	struct qdisc_walker *w);
1426
1427	static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
1428	{
1429	struct check_loop_arg arg;
1430
1431	if (q->ops->cl_ops == NULL)
1432	return 0;
1433
1434	arg.w.stop = arg.w.skip = arg.w.count = 0;
1435	arg.w.fn = check_loop_fn;
1436	arg.depth = depth;
1437	arg.p = p;
1438	q->ops->cl_ops->walk(q, &arg.w);
1439	return arg.w.stop ? -ELOOP : 0;
1440	}
1441
1442	static int
1443	check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
1444	{
1445	struct Qdisc *leaf;
1446	const struct Qdisc_class_ops *cops = q->ops->cl_ops;
1447	struct check_loop_arg *arg = (struct check_loop_arg *)w;
1448
1449	leaf = cops->leaf(q, cl);
1450	if (leaf) {
1451	if (leaf == arg->p || arg->depth > 7)
1452	return -ELOOP;
1453	return check_loop(q: leaf, p: arg->p, depth: arg->depth + 1);
1454	}
1455	return 0;
1456	}
1457
1458	const struct nla_policy rtm_tca_policy[TCA_MAX + 1] = {
1459	[TCA_KIND] = { .type = NLA_STRING },
1460	[TCA_RATE] = { .type = NLA_BINARY,
1461	.len = sizeof(struct tc_estimator) },
1462	[TCA_STAB] = { .type = NLA_NESTED },
1463	[TCA_DUMP_INVISIBLE] = { .type = NLA_FLAG },
1464	[TCA_CHAIN] = { .type = NLA_U32 },
1465	[TCA_INGRESS_BLOCK] = { .type = NLA_U32 },
1466	[TCA_EGRESS_BLOCK] = { .type = NLA_U32 },
1467	};
1468
1469	/*
1470	* Delete/get qdisc.
1471	*/
1472
1473	static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
1474	struct netlink_ext_ack *extack)
1475	{
1476	struct net *net = sock_net(sk: skb->sk);
1477	struct tcmsg *tcm = nlmsg_data(nlh: n);
1478	struct nlattr *tca[TCA_MAX + 1];
1479	struct net_device *dev;
1480	u32 clid;
1481	struct Qdisc *q = NULL;
1482	struct Qdisc *p = NULL;
1483	int err;
1484
1485	err = nlmsg_parse_deprecated(nlh: n, hdrlen: sizeof(*tcm), tb: tca, TCA_MAX,
1486	policy: rtm_tca_policy, extack);
1487	if (err < 0)
1488	return err;
1489
1490	dev = __dev_get_by_index(net, ifindex: tcm->tcm_ifindex);
1491	if (!dev)
1492	return -ENODEV;
1493
1494	clid = tcm->tcm_parent;
1495	if (clid) {
1496	if (clid != TC_H_ROOT) {
1497	if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
1498	p = qdisc_lookup(dev, TC_H_MAJ(clid));
1499	if (!p) {
1500	NL_SET_ERR_MSG(extack, "Failed to find qdisc with specified classid");
1501	return -ENOENT;
1502	}
1503	q = qdisc_leaf(p, classid: clid);
1504	} else if (dev_ingress_queue(dev)) {
1505	q = rtnl_dereference(dev_ingress_queue(dev)->qdisc_sleeping);
1506	}
1507	} else {
1508	q = rtnl_dereference(dev->qdisc);
1509	}
1510	if (!q) {
1511	NL_SET_ERR_MSG(extack, "Cannot find specified qdisc on specified device");
1512	return -ENOENT;
1513	}
1514
1515	if (tcm->tcm_handle && q->handle != tcm->tcm_handle) {
1516	NL_SET_ERR_MSG(extack, "Invalid handle");
1517	return -EINVAL;
1518	}
1519	} else {
1520	q = qdisc_lookup(dev, handle: tcm->tcm_handle);
1521	if (!q) {
1522	NL_SET_ERR_MSG(extack, "Failed to find qdisc with specified handle");
1523	return -ENOENT;
1524	}
1525	}
1526
1527	if (tca[TCA_KIND] && nla_strcmp(nla: tca[TCA_KIND], str: q->ops->id)) {
1528	NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1529	return -EINVAL;
1530	}
1531
1532	if (n->nlmsg_type == RTM_DELQDISC) {
1533	if (!clid) {
1534	NL_SET_ERR_MSG(extack, "Classid cannot be zero");
1535	return -EINVAL;
1536	}
1537	if (q->handle == 0) {
1538	NL_SET_ERR_MSG(extack, "Cannot delete qdisc with handle of zero");
1539	return -ENOENT;
1540	}
1541	err = qdisc_graft(dev, parent: p, skb, n, classid: clid, NULL, old: q, extack);
1542	if (err != 0)
1543	return err;
1544	} else {
1545	qdisc_notify(net, oskb: skb, n, clid, NULL, new: q, NULL);
1546	}
1547	return 0;
1548	}
1549
1550	static bool req_create_or_replace(struct nlmsghdr *n)
1551	{
1552	return (n->nlmsg_flags & NLM_F_CREATE &&
1553	n->nlmsg_flags & NLM_F_REPLACE);
1554	}
1555
1556	static bool req_create_exclusive(struct nlmsghdr *n)
1557	{
1558	return (n->nlmsg_flags & NLM_F_CREATE &&
1559	n->nlmsg_flags & NLM_F_EXCL);
1560	}
1561
1562	static bool req_change(struct nlmsghdr *n)
1563	{
1564	return (!(n->nlmsg_flags & NLM_F_CREATE) &&
1565	!(n->nlmsg_flags & NLM_F_REPLACE) &&
1566	!(n->nlmsg_flags & NLM_F_EXCL));
1567	}
1568
1569	/*
1570	* Create/change qdisc.
1571	*/
1572	static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
1573	struct netlink_ext_ack *extack)
1574	{
1575	struct net *net = sock_net(sk: skb->sk);
1576	struct tcmsg *tcm;
1577	struct nlattr *tca[TCA_MAX + 1];
1578	struct net_device *dev;
1579	u32 clid;
1580	struct Qdisc *q, *p;
1581	int err;
1582
1583	replay:
1584	/* Reinit, just in case something touches this. */
1585	err = nlmsg_parse_deprecated(nlh: n, hdrlen: sizeof(*tcm), tb: tca, TCA_MAX,
1586	policy: rtm_tca_policy, extack);
1587	if (err < 0)
1588	return err;
1589
1590	tcm = nlmsg_data(nlh: n);
1591	clid = tcm->tcm_parent;
1592	q = p = NULL;
1593
1594	dev = __dev_get_by_index(net, ifindex: tcm->tcm_ifindex);
1595	if (!dev)
1596	return -ENODEV;
1597
1598
1599	if (clid) {
1600	if (clid != TC_H_ROOT) {
1601	if (clid != TC_H_INGRESS) {
1602	p = qdisc_lookup(dev, TC_H_MAJ(clid));
1603	if (!p) {
1604	NL_SET_ERR_MSG(extack, "Failed to find specified qdisc");
1605	return -ENOENT;
1606	}
1607	q = qdisc_leaf(p, classid: clid);
1608	} else if (dev_ingress_queue_create(dev)) {
1609	q = rtnl_dereference(dev_ingress_queue(dev)->qdisc_sleeping);
1610	}
1611	} else {
1612	q = rtnl_dereference(dev->qdisc);
1613	}
1614
1615	/* It may be default qdisc, ignore it */
1616	if (q && q->handle == 0)
1617	q = NULL;
1618
1619	if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
1620	if (tcm->tcm_handle) {
1621	if (q && !(n->nlmsg_flags & NLM_F_REPLACE)) {
1622	NL_SET_ERR_MSG(extack, "NLM_F_REPLACE needed to override");
1623	return -EEXIST;
1624	}
1625	if (TC_H_MIN(tcm->tcm_handle)) {
1626	NL_SET_ERR_MSG(extack, "Invalid minor handle");
1627	return -EINVAL;
1628	}
1629	q = qdisc_lookup(dev, handle: tcm->tcm_handle);
1630	if (!q)
1631	goto create_n_graft;
1632	if (n->nlmsg_flags & NLM_F_EXCL) {
1633	NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot override");
1634	return -EEXIST;
1635	}
1636	if (tca[TCA_KIND] &&
1637	nla_strcmp(nla: tca[TCA_KIND], str: q->ops->id)) {
1638	NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1639	return -EINVAL;
1640	}
1641	if (q->flags & TCQ_F_INGRESS) {
1642	NL_SET_ERR_MSG(extack,
1643	"Cannot regraft ingress or clsact Qdiscs");
1644	return -EINVAL;
1645	}
1646	if (q == p ||
1647	(p && check_loop(q, p, depth: 0))) {
1648	NL_SET_ERR_MSG(extack, "Qdisc parent/child loop detected");
1649	return -ELOOP;
1650	}
1651	if (clid == TC_H_INGRESS) {
1652	NL_SET_ERR_MSG(extack, "Ingress cannot graft directly");
1653	return -EINVAL;
1654	}
1655	qdisc_refcount_inc(qdisc: q);
1656	goto graft;
1657	} else {
1658	if (!q)
1659	goto create_n_graft;
1660
1661	/* This magic test requires explanation.
1662	*
1663	* We know, that some child q is already
1664	* attached to this parent and have choice:
1665	* 1) change it or 2) create/graft new one.
1666	* If the requested qdisc kind is different
1667	* than the existing one, then we choose graft.
1668	* If they are the same then this is "change"
1669	* operation - just let it fallthrough..
1670	*
1671	* 1. We are allowed to create/graft only
1672	* if the request is explicitly stating
1673	* "please create if it doesn't exist".
1674	*
1675	* 2. If the request is to exclusive create
1676	* then the qdisc tcm_handle is not expected
1677	* to exist, so that we choose create/graft too.
1678	*
1679	* 3. The last case is when no flags are set.
1680	* This will happen when for example tc
1681	* utility issues a "change" command.
1682	* Alas, it is sort of hole in API, we
1683	* cannot decide what to do unambiguously.
1684	* For now we select create/graft.
1685	*/
1686	if (tca[TCA_KIND] &&
1687	nla_strcmp(nla: tca[TCA_KIND], str: q->ops->id)) {
1688	if (req_create_or_replace(n) ||
1689	req_create_exclusive(n))
1690	goto create_n_graft;
1691	else if (req_change(n))
1692	goto create_n_graft2;
1693	}
1694	}
1695	}
1696	} else {
1697	if (!tcm->tcm_handle) {
1698	NL_SET_ERR_MSG(extack, "Handle cannot be zero");
1699	return -EINVAL;
1700	}
1701	q = qdisc_lookup(dev, handle: tcm->tcm_handle);
1702	}
1703
1704	/* Change qdisc parameters */
1705	if (!q) {
1706	NL_SET_ERR_MSG(extack, "Specified qdisc not found");
1707	return -ENOENT;
1708	}
1709	if (n->nlmsg_flags & NLM_F_EXCL) {
1710	NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot modify");
1711	return -EEXIST;
1712	}
1713	if (tca[TCA_KIND] && nla_strcmp(nla: tca[TCA_KIND], str: q->ops->id)) {
1714	NL_SET_ERR_MSG(extack, "Invalid qdisc name");
1715	return -EINVAL;
1716	}
1717	err = qdisc_change(sch: q, tca, extack);
1718	if (err == 0)
1719	qdisc_notify(net, oskb: skb, n, clid, NULL, new: q, extack);
1720	return err;
1721
1722	create_n_graft:
1723	if (!(n->nlmsg_flags & NLM_F_CREATE)) {
1724	NL_SET_ERR_MSG(extack, "Qdisc not found. To create specify NLM_F_CREATE flag");
1725	return -ENOENT;
1726	}
1727	create_n_graft2:
1728	if (clid == TC_H_INGRESS) {
1729	if (dev_ingress_queue(dev)) {
1730	q = qdisc_create(dev, dev_queue: dev_ingress_queue(dev),
1731	parent: tcm->tcm_parent, handle: tcm->tcm_parent,
1732	tca, errp: &err, extack);
1733	} else {
1734	NL_SET_ERR_MSG(extack, "Cannot find ingress queue for specified device");
1735	err = -ENOENT;
1736	}
1737	} else {
1738	struct netdev_queue *dev_queue;
1739
1740	if (p && p->ops->cl_ops && p->ops->cl_ops->select_queue)
1741	dev_queue = p->ops->cl_ops->select_queue(p, tcm);
1742	else if (p)
1743	dev_queue = p->dev_queue;
1744	else
1745	dev_queue = netdev_get_tx_queue(dev, index: 0);
1746
1747	q = qdisc_create(dev, dev_queue,
1748	parent: tcm->tcm_parent, handle: tcm->tcm_handle,
1749	tca, errp: &err, extack);
1750	}
1751	if (q == NULL) {
1752	if (err == -EAGAIN)
1753	goto replay;
1754	return err;
1755	}
1756
1757	graft:
1758	err = qdisc_graft(dev, parent: p, skb, n, classid: clid, new: q, NULL, extack);
1759	if (err) {
1760	if (q)
1761	qdisc_put(qdisc: q);
1762	return err;
1763	}
1764
1765	return 0;
1766	}
1767
1768	static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
1769	struct netlink_callback *cb,
1770	int *q_idx_p, int s_q_idx, bool recur,
1771	bool dump_invisible)
1772	{
1773	int ret = 0, q_idx = *q_idx_p;
1774	struct Qdisc *q;
1775	int b;
1776
1777	if (!root)
1778	return 0;
1779
1780	q = root;
1781	if (q_idx < s_q_idx) {
1782	q_idx++;
1783	} else {
1784	if (!tc_qdisc_dump_ignore(q, dump_invisible) &&
1785	tc_fill_qdisc(skb, q, clid: q->parent, NETLINK_CB(cb->skb).portid,
1786	seq: cb->nlh->nlmsg_seq, NLM_F_MULTI,
1787	RTM_NEWQDISC, NULL) <= 0)
1788	goto done;
1789	q_idx++;
1790	}
1791
1792	/* If dumping singletons, there is no qdisc_dev(root) and the singleton
1793	* itself has already been dumped.
1794	*
1795	* If we've already dumped the top-level (ingress) qdisc above and the global
1796	* qdisc hashtable, we don't want to hit it again
1797	*/
1798	if (!qdisc_dev(qdisc: root) || !recur)
1799	goto out;
1800
1801	hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
1802	if (q_idx < s_q_idx) {
1803	q_idx++;
1804	continue;
1805	}
1806	if (!tc_qdisc_dump_ignore(q, dump_invisible) &&
1807	tc_fill_qdisc(skb, q, clid: q->parent, NETLINK_CB(cb->skb).portid,
1808	seq: cb->nlh->nlmsg_seq, NLM_F_MULTI,
1809	RTM_NEWQDISC, NULL) <= 0)
1810	goto done;
1811	q_idx++;
1812	}
1813
1814	out:
1815	*q_idx_p = q_idx;
1816	return ret;
1817	done:
1818	ret = -1;
1819	goto out;
1820	}
1821
1822	static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
1823	{
1824	struct net *net = sock_net(sk: skb->sk);
1825	int idx, q_idx;
1826	int s_idx, s_q_idx;
1827	struct net_device *dev;
1828	const struct nlmsghdr *nlh = cb->nlh;
1829	struct nlattr *tca[TCA_MAX + 1];
1830	int err;
1831
1832	s_idx = cb->args[0];
1833	s_q_idx = q_idx = cb->args[1];
1834
1835	idx = 0;
1836	ASSERT_RTNL();
1837
1838	err = nlmsg_parse_deprecated(nlh, hdrlen: sizeof(struct tcmsg), tb: tca, TCA_MAX,
1839	policy: rtm_tca_policy, extack: cb->extack);
1840	if (err < 0)
1841	return err;
1842
1843	for_each_netdev(net, dev) {
1844	struct netdev_queue *dev_queue;
1845
1846	if (idx < s_idx)
1847	goto cont;
1848	if (idx > s_idx)
1849	s_q_idx = 0;
1850	q_idx = 0;
1851
1852	if (tc_dump_qdisc_root(rtnl_dereference(dev->qdisc),
1853	skb, cb, q_idx_p: &q_idx, s_q_idx,
1854	recur: true, dump_invisible: tca[TCA_DUMP_INVISIBLE]) < 0)
1855	goto done;
1856
1857	dev_queue = dev_ingress_queue(dev);
1858	if (dev_queue &&
1859	tc_dump_qdisc_root(rtnl_dereference(dev_queue->qdisc_sleeping),
1860	skb, cb, q_idx_p: &q_idx, s_q_idx, recur: false,
1861	dump_invisible: tca[TCA_DUMP_INVISIBLE]) < 0)
1862	goto done;
1863
1864	cont:
1865	idx++;
1866	}
1867
1868	done:
1869	cb->args[0] = idx;
1870	cb->args[1] = q_idx;
1871
1872	return skb->len;
1873	}
1874
1875
1876
1877	/************************************************
1878	* Traffic classes manipulation. *
1879	************************************************/
1880
1881	static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1882	unsigned long cl, u32 portid, u32 seq, u16 flags,
1883	int event, struct netlink_ext_ack *extack)
1884	{
1885	struct tcmsg *tcm;
1886	struct nlmsghdr *nlh;
1887	unsigned char *b = skb_tail_pointer(skb);
1888	struct gnet_dump d;
1889	const struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1890
1891	cond_resched();
1892	nlh = nlmsg_put(skb, portid, seq, type: event, payload: sizeof(*tcm), flags);
1893	if (!nlh)
1894	goto out_nlmsg_trim;
1895	tcm = nlmsg_data(nlh);
1896	tcm->tcm_family = AF_UNSPEC;
1897	tcm->tcm__pad1 = 0;
1898	tcm->tcm__pad2 = 0;
1899	tcm->tcm_ifindex = qdisc_dev(qdisc: q)->ifindex;
1900	tcm->tcm_parent = q->handle;
1901	tcm->tcm_handle = q->handle;
1902	tcm->tcm_info = 0;
1903	if (nla_put_string(skb, attrtype: TCA_KIND, str: q->ops->id))
1904	goto nla_put_failure;
1905	if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1906	goto nla_put_failure;
1907
1908	if (gnet_stats_start_copy_compat(skb, type: TCA_STATS2, tc_stats_type: TCA_STATS, xstats_type: TCA_XSTATS,
1909	NULL, d: &d, padattr: TCA_PAD) < 0)
1910	goto nla_put_failure;
1911
1912	if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1913	goto nla_put_failure;
1914
1915	if (gnet_stats_finish_copy(d: &d) < 0)
1916	goto nla_put_failure;
1917
1918	if (extack && extack->_msg &&
1919	nla_put_string(skb, attrtype: TCA_EXT_WARN_MSG, str: extack->_msg))
1920	goto out_nlmsg_trim;
1921
1922	nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1923
1924	return skb->len;
1925
1926	out_nlmsg_trim:
1927	nla_put_failure:
1928	nlmsg_trim(skb, mark: b);
1929	return -1;
1930	}
1931
1932	static int tclass_notify(struct net *net, struct sk_buff *oskb,
1933	struct nlmsghdr *n, struct Qdisc *q,
1934	unsigned long cl, int event, struct netlink_ext_ack *extack)
1935	{
1936	struct sk_buff *skb;
1937	u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
1938
1939	skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1940	if (!skb)
1941	return -ENOBUFS;
1942
1943	if (tc_fill_tclass(skb, q, cl, portid, seq: n->nlmsg_seq, flags: 0, event, extack) < 0) {
1944	kfree_skb(skb);
1945	return -EINVAL;
1946	}
1947
1948	return rtnetlink_send(skb, net, pid: portid, RTNLGRP_TC,
1949	echo: n->nlmsg_flags & NLM_F_ECHO);
1950	}
1951
1952	static int tclass_del_notify(struct net *net,
1953	const struct Qdisc_class_ops *cops,
1954	struct sk_buff *oskb, struct nlmsghdr *n,
1955	struct Qdisc *q, unsigned long cl,
1956	struct netlink_ext_ack *extack)
1957	{
1958	u32 portid = oskb ? NETLINK_CB(oskb).portid : 0;
1959	struct sk_buff *skb;
1960	int err = 0;
1961
1962	if (!cops->delete)
1963	return -EOPNOTSUPP;
1964
1965	skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1966	if (!skb)
1967	return -ENOBUFS;
1968
1969	if (tc_fill_tclass(skb, q, cl, portid, seq: n->nlmsg_seq, flags: 0,
1970	RTM_DELTCLASS, extack) < 0) {
1971	kfree_skb(skb);
1972	return -EINVAL;
1973	}
1974
1975	err = cops->delete(q, cl, extack);
1976	if (err) {
1977	kfree_skb(skb);
1978	return err;
1979	}
1980
1981	err = rtnetlink_send(skb, net, pid: portid, RTNLGRP_TC,
1982	echo: n->nlmsg_flags & NLM_F_ECHO);
1983	return err;
1984	}
1985
1986	#ifdef CONFIG_NET_CLS
1987
1988	struct tcf_bind_args {
1989	struct tcf_walker w;
1990	unsigned long base;
1991	unsigned long cl;
1992	u32 classid;
1993	};
1994
1995	static int tcf_node_bind(struct tcf_proto *tp, void *n, struct tcf_walker *arg)
1996	{
1997	struct tcf_bind_args *a = (void *)arg;
1998
1999	if (n && tp->ops->bind_class) {
2000	struct Qdisc *q = tcf_block_q(block: tp->chain->block);
2001
2002	sch_tree_lock(q);
2003	tp->ops->bind_class(n, a->classid, a->cl, q, a->base);
2004	sch_tree_unlock(q);
2005	}
2006	return 0;
2007	}
2008
2009	struct tc_bind_class_args {
2010	struct qdisc_walker w;
2011	unsigned long new_cl;
2012	u32 portid;
2013	u32 clid;
2014	};
2015
2016	static int tc_bind_class_walker(struct Qdisc *q, unsigned long cl,
2017	struct qdisc_walker *w)
2018	{
2019	struct tc_bind_class_args *a = (struct tc_bind_class_args *)w;
2020	const struct Qdisc_class_ops *cops = q->ops->cl_ops;
2021	struct tcf_block *block;
2022	struct tcf_chain *chain;
2023
2024	block = cops->tcf_block(q, cl, NULL);
2025	if (!block)
2026	return 0;
2027	for (chain = tcf_get_next_chain(block, NULL);
2028	chain;
2029	chain = tcf_get_next_chain(block, chain)) {
2030	struct tcf_proto *tp;
2031
2032	for (tp = tcf_get_next_proto(chain, NULL);
2033	tp; tp = tcf_get_next_proto(chain, tp)) {
2034	struct tcf_bind_args arg = {};
2035
2036	arg.w.fn = tcf_node_bind;
2037	arg.classid = a->clid;
2038	arg.base = cl;
2039	arg.cl = a->new_cl;
2040	tp->ops->walk(tp, &arg.w, true);
2041	}
2042	}
2043
2044	return 0;
2045	}
2046
2047	static void tc_bind_tclass(struct Qdisc *q, u32 portid, u32 clid,
2048	unsigned long new_cl)
2049	{
2050	const struct Qdisc_class_ops *cops = q->ops->cl_ops;
2051	struct tc_bind_class_args args = {};
2052
2053	if (!cops->tcf_block)
2054	return;
2055	args.portid = portid;
2056	args.clid = clid;
2057	args.new_cl = new_cl;
2058	args.w.fn = tc_bind_class_walker;
2059	q->ops->cl_ops->walk(q, &args.w);
2060	}
2061
2062	#else
2063
2064	static void tc_bind_tclass(struct Qdisc *q, u32 portid, u32 clid,
2065	unsigned long new_cl)
2066	{
2067	}
2068
2069	#endif
2070
2071	static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n,
2072	struct netlink_ext_ack *extack)
2073	{
2074	struct net *net = sock_net(sk: skb->sk);
2075	struct tcmsg *tcm = nlmsg_data(nlh: n);
2076	struct nlattr *tca[TCA_MAX + 1];
2077	struct net_device *dev;
2078	struct Qdisc *q = NULL;
2079	const struct Qdisc_class_ops *cops;
2080	unsigned long cl = 0;
2081	unsigned long new_cl;
2082	u32 portid;
2083	u32 clid;
2084	u32 qid;
2085	int err;
2086
2087	err = nlmsg_parse_deprecated(nlh: n, hdrlen: sizeof(*tcm), tb: tca, TCA_MAX,
2088	policy: rtm_tca_policy, extack);
2089	if (err < 0)
2090	return err;
2091
2092	dev = __dev_get_by_index(net, ifindex: tcm->tcm_ifindex);
2093	if (!dev)
2094	return -ENODEV;
2095
2096	/*
2097	parent == TC_H_UNSPEC - unspecified parent.
2098	parent == TC_H_ROOT - class is root, which has no parent.
2099	parent == X:0 - parent is root class.
2100	parent == X:Y - parent is a node in hierarchy.
2101	parent == 0:Y - parent is X:Y, where X:0 is qdisc.
2102
2103	handle == 0:0 - generate handle from kernel pool.
2104	handle == 0:Y - class is X:Y, where X:0 is qdisc.
2105	handle == X:Y - clear.
2106	handle == X:0 - root class.
2107	*/
2108
2109	/* Step 1. Determine qdisc handle X:0 */
2110
2111	portid = tcm->tcm_parent;
2112	clid = tcm->tcm_handle;
2113	qid = TC_H_MAJ(clid);
2114
2115	if (portid != TC_H_ROOT) {
2116	u32 qid1 = TC_H_MAJ(portid);
2117
2118	if (qid && qid1) {
2119	/* If both majors are known, they must be identical. */
2120	if (qid != qid1)
2121	return -EINVAL;
2122	} else if (qid1) {
2123	qid = qid1;
2124	} else if (qid == 0)
2125	qid = rtnl_dereference(dev->qdisc)->handle;
2126
2127	/* Now qid is genuine qdisc handle consistent
2128	* both with parent and child.
2129	*
2130	* TC_H_MAJ(portid) still may be unspecified, complete it now.
2131	*/
2132	if (portid)
2133	portid = TC_H_MAKE(qid, portid);
2134	} else {
2135	if (qid == 0)
2136	qid = rtnl_dereference(dev->qdisc)->handle;
2137	}
2138
2139	/* OK. Locate qdisc */
2140	q = qdisc_lookup(dev, handle: qid);
2141	if (!q)
2142	return -ENOENT;
2143
2144	/* An check that it supports classes */
2145	cops = q->ops->cl_ops;
2146	if (cops == NULL)
2147	return -EINVAL;
2148
2149	/* Now try to get class */
2150	if (clid == 0) {
2151	if (portid == TC_H_ROOT)
2152	clid = qid;
2153	} else
2154	clid = TC_H_MAKE(qid, clid);
2155
2156	if (clid)
2157	cl = cops->find(q, clid);
2158
2159	if (cl == 0) {
2160	err = -ENOENT;
2161	if (n->nlmsg_type != RTM_NEWTCLASS ||
2162	!(n->nlmsg_flags & NLM_F_CREATE))
2163	goto out;
2164	} else {
2165	switch (n->nlmsg_type) {
2166	case RTM_NEWTCLASS:
2167	err = -EEXIST;
2168	if (n->nlmsg_flags & NLM_F_EXCL)
2169	goto out;
2170	break;
2171	case RTM_DELTCLASS:
2172	err = tclass_del_notify(net, cops, oskb: skb, n, q, cl, extack);
2173	/* Unbind the class with flilters with 0 */
2174	tc_bind_tclass(q, portid, clid, new_cl: 0);
2175	goto out;
2176	case RTM_GETTCLASS:
2177	err = tclass_notify(net, oskb: skb, n, q, cl, RTM_NEWTCLASS, extack);
2178	goto out;
2179	default:
2180	err = -EINVAL;
2181	goto out;
2182	}
2183	}
2184
2185	if (tca[TCA_INGRESS_BLOCK] || tca[TCA_EGRESS_BLOCK]) {
2186	NL_SET_ERR_MSG(extack, "Shared blocks are not supported for classes");
2187	return -EOPNOTSUPP;
2188	}
2189
2190	new_cl = cl;
2191	err = -EOPNOTSUPP;
2192	if (cops->change)
2193	err = cops->change(q, clid, portid, tca, &new_cl, extack);
2194	if (err == 0) {
2195	tclass_notify(net, oskb: skb, n, q, cl: new_cl, RTM_NEWTCLASS, extack);
2196	/* We just create a new class, need to do reverse binding. */
2197	if (cl != new_cl)
2198	tc_bind_tclass(q, portid, clid, new_cl);
2199	}
2200	out:
2201	return err;
2202	}
2203
2204	struct qdisc_dump_args {
2205	struct qdisc_walker w;
2206	struct sk_buff *skb;
2207	struct netlink_callback *cb;
2208	};
2209
2210	static int qdisc_class_dump(struct Qdisc *q, unsigned long cl,
2211	struct qdisc_walker *arg)
2212	{
2213	struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
2214
2215	return tc_fill_tclass(skb: a->skb, q, cl, NETLINK_CB(a->cb->skb).portid,
2216	seq: a->cb->nlh->nlmsg_seq, NLM_F_MULTI,
2217	RTM_NEWTCLASS, NULL);
2218	}
2219
2220	static int tc_dump_tclass_qdisc(struct Qdisc *q, struct sk_buff *skb,
2221	struct tcmsg *tcm, struct netlink_callback *cb,
2222	int *t_p, int s_t)
2223	{
2224	struct qdisc_dump_args arg;
2225
2226	if (tc_qdisc_dump_ignore(q, dump_invisible: false) ||
2227	*t_p < s_t || !q->ops->cl_ops ||
2228	(tcm->tcm_parent &&
2229	TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
2230	(*t_p)++;
2231	return 0;
2232	}
2233	if (*t_p > s_t)
2234	memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
2235	arg.w.fn = qdisc_class_dump;
2236	arg.skb = skb;
2237	arg.cb = cb;
2238	arg.w.stop = 0;
2239	arg.w.skip = cb->args[1];
2240	arg.w.count = 0;
2241	q->ops->cl_ops->walk(q, &arg.w);
2242	cb->args[1] = arg.w.count;
2243	if (arg.w.stop)
2244	return -1;
2245	(*t_p)++;
2246	return 0;
2247	}
2248
2249	static int tc_dump_tclass_root(struct Qdisc *root, struct sk_buff *skb,
2250	struct tcmsg *tcm, struct netlink_callback *cb,
2251	int *t_p, int s_t, bool recur)
2252	{
2253	struct Qdisc *q;
2254	int b;
2255
2256	if (!root)
2257	return 0;
2258
2259	if (tc_dump_tclass_qdisc(q: root, skb, tcm, cb, t_p, s_t) < 0)
2260	return -1;
2261
2262	if (!qdisc_dev(qdisc: root) || !recur)
2263	return 0;
2264
2265	if (tcm->tcm_parent) {
2266	q = qdisc_match_from_root(root, TC_H_MAJ(tcm->tcm_parent));
2267	if (q && q != root &&
2268	tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
2269	return -1;
2270	return 0;
2271	}
2272	hash_for_each(qdisc_dev(root)->qdisc_hash, b, q, hash) {
2273	if (tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
2274	return -1;
2275	}
2276
2277	return 0;
2278	}
2279
2280	static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
2281	{
2282	struct tcmsg *tcm = nlmsg_data(nlh: cb->nlh);
2283	struct net *net = sock_net(sk: skb->sk);
2284	struct netdev_queue *dev_queue;
2285	struct net_device *dev;
2286	int t, s_t;
2287
2288	if (nlmsg_len(nlh: cb->nlh) < sizeof(*tcm))
2289	return 0;
2290	dev = dev_get_by_index(net, ifindex: tcm->tcm_ifindex);
2291	if (!dev)
2292	return 0;
2293
2294	s_t = cb->args[0];
2295	t = 0;
2296
2297	if (tc_dump_tclass_root(rtnl_dereference(dev->qdisc),
2298	skb, tcm, cb, t_p: &t, s_t, recur: true) < 0)
2299	goto done;
2300
2301	dev_queue = dev_ingress_queue(dev);
2302	if (dev_queue &&
2303	tc_dump_tclass_root(rtnl_dereference(dev_queue->qdisc_sleeping),
2304	skb, tcm, cb, t_p: &t, s_t, recur: false) < 0)
2305	goto done;
2306
2307	done:
2308	cb->args[0] = t;
2309
2310	dev_put(dev);
2311	return skb->len;
2312	}
2313
2314	#ifdef CONFIG_PROC_FS
2315	static int psched_show(struct seq_file *seq, void *v)
2316	{
2317	seq_printf(m: seq, fmt: "%08x %08x %08x %08x\n",
2318	(u32)NSEC_PER_USEC, (u32)PSCHED_TICKS2NS(1),
2319	1000000,
2320	(u32)NSEC_PER_SEC / hrtimer_resolution);
2321
2322	return 0;
2323	}
2324
2325	static int __net_init psched_net_init(struct net *net)
2326	{
2327	struct proc_dir_entry *e;
2328
2329	e = proc_create_single("psched", 0, net->proc_net, psched_show);
2330	if (e == NULL)
2331	return -ENOMEM;
2332
2333	return 0;
2334	}
2335
2336	static void __net_exit psched_net_exit(struct net *net)
2337	{
2338	remove_proc_entry("psched", net->proc_net);
2339	}
2340	#else
2341	static int __net_init psched_net_init(struct net *net)
2342	{
2343	return 0;
2344	}
2345
2346	static void __net_exit psched_net_exit(struct net *net)
2347	{
2348	}
2349	#endif
2350
2351	static struct pernet_operations psched_net_ops = {
2352	.init = psched_net_init,
2353	.exit = psched_net_exit,
2354	};
2355
2356	#if IS_ENABLED(CONFIG_RETPOLINE)
2357	DEFINE_STATIC_KEY_FALSE(tc_skip_wrapper);
2358	#endif
2359
2360	static int __init pktsched_init(void)
2361	{
2362	int err;
2363
2364	err = register_pernet_subsys(&psched_net_ops);
2365	if (err) {
2366	pr_err("pktsched_init: "
2367	"cannot initialize per netns operations\n");
2368	return err;
2369	}
2370
2371	register_qdisc(&pfifo_fast_ops);
2372	register_qdisc(&pfifo_qdisc_ops);
2373	register_qdisc(&bfifo_qdisc_ops);
2374	register_qdisc(&pfifo_head_drop_qdisc_ops);
2375	register_qdisc(&mq_qdisc_ops);
2376	register_qdisc(&noqueue_qdisc_ops);
2377
2378	rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL, flags: 0);
2379	rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL, flags: 0);
2380	rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc,
2381	flags: 0);
2382	rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL, flags: 0);
2383	rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL, flags: 0);
2384	rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass,
2385	flags: 0);
2386
2387	tc_wrapper_init();
2388
2389	return 0;
2390	}
2391
2392	subsys_initcall(pktsched_init);
2393