blob: 4d2b37226e75c495b58cdf5b6dceb88336989321 [file] [log] [blame]
Greg Kroah-Hartmanb2441312017-11-01 15:07:57 +01001/* SPDX-License-Identifier: GPL-2.0 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002#ifndef __NET_SCHED_GENERIC_H
3#define __NET_SCHED_GENERIC_H
4
Linus Torvalds1da177e2005-04-16 15:20:36 -07005#include <linux/netdevice.h>
6#include <linux/types.h>
7#include <linux/rcupdate.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -07008#include <linux/pkt_sched.h>
9#include <linux/pkt_cls.h>
John Fastabend22e0f8b2014-09-28 11:52:56 -070010#include <linux/percpu.h>
Jesper Dangaard Brouer5772e9a2014-10-01 22:35:59 +020011#include <linux/dynamic_queue_limits.h>
Jiri Pirko5bc17012017-05-17 11:08:01 +020012#include <linux/list.h>
Reshetova, Elena7b936402017-07-04 15:53:07 +030013#include <linux/refcount.h>
Cong Wang7aa00452017-10-26 18:24:28 -070014#include <linux/workqueue.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015#include <net/gen_stats.h>
Thomas Grafbe577dd2007-03-22 11:55:50 -070016#include <net/rtnetlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070017
18struct Qdisc_ops;
19struct qdisc_walker;
20struct tcf_walker;
21struct module;
22
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +000023struct qdisc_rate_table {
Linus Torvalds1da177e2005-04-16 15:20:36 -070024 struct tc_ratespec rate;
25 u32 data[256];
26 struct qdisc_rate_table *next;
27 int refcnt;
28};
29
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +000030enum qdisc_state_t {
David S. Miller37437bb2008-07-16 02:15:04 -070031 __QDISC_STATE_SCHED,
David S. Millera9312ae2008-08-17 21:51:03 -070032 __QDISC_STATE_DEACTIVATED,
John Fastabendeb82a992018-03-24 22:25:06 -070033 __QDISC_STATE_RUNNING,
David S. Millere2627c82008-07-16 00:56:32 -070034};
35
Jussi Kivilinna175f9c12008-07-20 00:08:47 -070036struct qdisc_size_table {
Eric Dumazeta2da5702011-01-20 03:48:19 +000037 struct rcu_head rcu;
Jussi Kivilinna175f9c12008-07-20 00:08:47 -070038 struct list_head list;
39 struct tc_sizespec szopts;
40 int refcnt;
41 u16 data[];
42};
43
Florian Westphal48da34b2016-09-18 00:57:34 +020044/* similar to sk_buff_head, but skb->prev pointer is undefined. */
45struct qdisc_skb_head {
46 struct sk_buff *head;
47 struct sk_buff *tail;
48 __u32 qlen;
49 spinlock_t lock;
50};
51
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +000052struct Qdisc {
Eric Dumazet520ac302016-06-21 23:16:49 -070053 int (*enqueue)(struct sk_buff *skb,
54 struct Qdisc *sch,
55 struct sk_buff **to_free);
56 struct sk_buff * (*dequeue)(struct Qdisc *sch);
Eric Dumazet05bdd2f2011-10-20 17:45:43 -040057 unsigned int flags;
Jarek Poplawskib00355d2009-02-01 01:12:42 -080058#define TCQ_F_BUILTIN 1
Eric Dumazetfd245a42011-01-20 05:27:16 +000059#define TCQ_F_INGRESS 2
60#define TCQ_F_CAN_BYPASS 4
61#define TCQ_F_MQROOT 8
Eric Dumazet1abbe132012-12-11 15:54:33 +000062#define TCQ_F_ONETXQUEUE 0x10 /* dequeue_skb() can assume all skbs are for
63 * q->dev_queue : It can test
64 * netif_xmit_frozen_or_stopped() before
65 * dequeueing next packet.
66 * Its true for MQ/MQPRIO slaves, or non
67 * multiqueue device.
68 */
Jarek Poplawskib00355d2009-02-01 01:12:42 -080069#define TCQ_F_WARN_NONWC (1 << 16)
John Fastabend22e0f8b2014-09-28 11:52:56 -070070#define TCQ_F_CPUSTATS 0x20 /* run using percpu statistics */
Eric Dumazet4eaf3b82015-12-01 20:08:51 -080071#define TCQ_F_NOPARENT 0x40 /* root of its hierarchy :
72 * qdisc_tree_decrease_qlen() should stop.
73 */
Jiri Kosina49b49972017-03-08 16:03:32 +010074#define TCQ_F_INVISIBLE 0x80 /* invisible by default in dump */
John Fastabend6b3ba912017-12-07 09:54:25 -080075#define TCQ_F_NOLOCK 0x100 /* qdisc does not require locking */
Yuval Mintz7a4fa292017-12-14 15:54:29 +020076#define TCQ_F_OFFLOADED 0x200 /* qdisc is offloaded to HW */
Eric Dumazet45203a32013-06-06 08:43:22 -070077 u32 limit;
Eric Dumazet05bdd2f2011-10-20 17:45:43 -040078 const struct Qdisc_ops *ops;
Eric Dumazeta2da5702011-01-20 03:48:19 +000079 struct qdisc_size_table __rcu *stab;
Jiri Kosina59cc1f62016-08-10 11:05:15 +020080 struct hlist_node hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -070081 u32 handle;
82 u32 parent;
David S. Miller72b25a92008-07-18 20:54:17 -070083
Eric Dumazet5e140df2009-03-20 01:33:32 -070084 struct netdev_queue *dev_queue;
Eric Dumazet5e140df2009-03-20 01:33:32 -070085
Eric Dumazet1c0d32f2016-12-04 09:48:16 -080086 struct net_rate_estimator __rcu *rate_est;
Eric Dumazet0d32ef82015-01-29 17:30:12 -080087 struct gnet_stats_basic_cpu __percpu *cpu_bstats;
88 struct gnet_stats_queue __percpu *cpu_qstats;
89
Eric Dumazet5e140df2009-03-20 01:33:32 -070090 /*
91 * For performance sake on SMP, we put highly modified fields at the end
92 */
John Fastabenda53851e2017-12-07 09:55:45 -080093 struct sk_buff_head gso_skb ____cacheline_aligned_in_smp;
Florian Westphal48da34b2016-09-18 00:57:34 +020094 struct qdisc_skb_head q;
Eric Dumazet0d32ef82015-01-29 17:30:12 -080095 struct gnet_stats_basic_packed bstats;
Eric Dumazetf9eb8ae2016-06-06 09:37:15 -070096 seqcount_t running;
Eric Dumazet0d32ef82015-01-29 17:30:12 -080097 struct gnet_stats_queue qstats;
Eric Dumazet4d202a02016-06-21 23:16:52 -070098 unsigned long state;
99 struct Qdisc *next_sched;
John Fastabend70e57d52017-12-07 09:56:23 -0800100 struct sk_buff_head skb_bad_txq;
Eric Dumazet45203a32013-06-06 08:43:22 -0700101 int padded;
Reshetova, Elena7b936402017-07-04 15:53:07 +0300102 refcount_t refcnt;
Eric Dumazet45203a32013-06-06 08:43:22 -0700103
104 spinlock_t busylock ____cacheline_aligned_in_smp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105};
106
Eric Dumazet551143d2017-08-24 21:12:28 -0700107static inline void qdisc_refcount_inc(struct Qdisc *qdisc)
108{
109 if (qdisc->flags & TCQ_F_BUILTIN)
110 return;
111 refcount_inc(&qdisc->refcnt);
112}
113
Eric Dumazetfd245a42011-01-20 05:27:16 +0000114static inline bool qdisc_is_running(const struct Qdisc *qdisc)
Eric Dumazetbc135b22010-06-02 03:23:51 -0700115{
Paolo Abeni32f7b442018-05-15 10:50:31 +0200116 if (qdisc->flags & TCQ_F_NOLOCK)
117 return test_bit(__QDISC_STATE_RUNNING, &qdisc->state);
Eric Dumazetf9eb8ae2016-06-06 09:37:15 -0700118 return (raw_read_seqcount(&qdisc->running) & 1) ? true : false;
Eric Dumazetbc135b22010-06-02 03:23:51 -0700119}
120
121static inline bool qdisc_run_begin(struct Qdisc *qdisc)
122{
Paolo Abeni32f7b442018-05-15 10:50:31 +0200123 if (qdisc->flags & TCQ_F_NOLOCK) {
124 if (test_and_set_bit(__QDISC_STATE_RUNNING, &qdisc->state))
125 return false;
126 } else if (qdisc_is_running(qdisc)) {
Eric Dumazetfd245a42011-01-20 05:27:16 +0000127 return false;
Paolo Abeni32f7b442018-05-15 10:50:31 +0200128 }
Eric Dumazet52fbb292016-06-09 07:45:11 -0700129 /* Variant of write_seqcount_begin() telling lockdep a trylock
130 * was attempted.
131 */
132 raw_write_seqcount_begin(&qdisc->running);
133 seqcount_acquire(&qdisc->running.dep_map, 0, 1, _RET_IP_);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000134 return true;
Eric Dumazetbc135b22010-06-02 03:23:51 -0700135}
136
137static inline void qdisc_run_end(struct Qdisc *qdisc)
138{
Eric Dumazetf9eb8ae2016-06-06 09:37:15 -0700139 write_seqcount_end(&qdisc->running);
Paolo Abeni32f7b442018-05-15 10:50:31 +0200140 if (qdisc->flags & TCQ_F_NOLOCK)
141 clear_bit(__QDISC_STATE_RUNNING, &qdisc->state);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000142}
143
Jesper Dangaard Brouer5772e9a2014-10-01 22:35:59 +0200144static inline bool qdisc_may_bulk(const struct Qdisc *qdisc)
145{
146 return qdisc->flags & TCQ_F_ONETXQUEUE;
147}
148
149static inline int qdisc_avail_bulklimit(const struct netdev_queue *txq)
150{
151#ifdef CONFIG_BQL
152 /* Non-BQL migrated drivers will return 0, too. */
153 return dql_avail(&txq->dql);
154#else
155 return 0;
156#endif
157}
158
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000159struct Qdisc_class_ops {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160 /* Child qdisc manipulation */
Jarek Poplawski926e61b2009-09-15 02:53:07 -0700161 struct netdev_queue * (*select_queue)(struct Qdisc *, struct tcmsg *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162 int (*graft)(struct Qdisc *, unsigned long cl,
Alexander Aring653d6fd2017-12-20 12:35:17 -0500163 struct Qdisc *, struct Qdisc **,
164 struct netlink_ext_ack *extack);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165 struct Qdisc * (*leaf)(struct Qdisc *, unsigned long cl);
Patrick McHardy43effa12006-11-29 17:35:48 -0800166 void (*qlen_notify)(struct Qdisc *, unsigned long);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167
168 /* Class manipulation routines */
WANG Cong143976c2017-08-24 16:51:29 -0700169 unsigned long (*find)(struct Qdisc *, u32 classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170 int (*change)(struct Qdisc *, u32, u32,
Alexander Aring793d81d2017-12-20 12:35:15 -0500171 struct nlattr **, unsigned long *,
172 struct netlink_ext_ack *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173 int (*delete)(struct Qdisc *, unsigned long);
174 void (*walk)(struct Qdisc *, struct qdisc_walker * arg);
175
176 /* Filter manipulation */
Alexander Aring0ac4bd62017-12-04 18:39:59 -0500177 struct tcf_block * (*tcf_block)(struct Qdisc *sch,
Alexander Aringcbaacc42017-12-20 12:35:16 -0500178 unsigned long arg,
179 struct netlink_ext_ack *extack);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180 unsigned long (*bind_tcf)(struct Qdisc *, unsigned long,
181 u32 classid);
182 void (*unbind_tcf)(struct Qdisc *, unsigned long);
183
184 /* rtnetlink specific */
185 int (*dump)(struct Qdisc *, unsigned long,
186 struct sk_buff *skb, struct tcmsg*);
187 int (*dump_stats)(struct Qdisc *, unsigned long,
188 struct gnet_dump *);
189};
190
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000191struct Qdisc_ops {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192 struct Qdisc_ops *next;
Eric Dumazet20fea082007-11-14 01:44:41 -0800193 const struct Qdisc_class_ops *cl_ops;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194 char id[IFNAMSIZ];
195 int priv_size;
John Fastabendd59f5ff2017-12-07 09:55:26 -0800196 unsigned int static_flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700197
Eric Dumazet520ac302016-06-21 23:16:49 -0700198 int (*enqueue)(struct sk_buff *skb,
199 struct Qdisc *sch,
200 struct sk_buff **to_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 struct sk_buff * (*dequeue)(struct Qdisc *);
Jarek Poplawski90d841fd2008-10-31 00:43:45 -0700202 struct sk_buff * (*peek)(struct Qdisc *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203
Alexander Aringe63d7df2017-12-20 12:35:13 -0500204 int (*init)(struct Qdisc *sch, struct nlattr *arg,
205 struct netlink_ext_ack *extack);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206 void (*reset)(struct Qdisc *);
207 void (*destroy)(struct Qdisc *);
Alexander Aring0ac4bd62017-12-04 18:39:59 -0500208 int (*change)(struct Qdisc *sch,
Alexander Aring20307212017-12-20 12:35:14 -0500209 struct nlattr *arg,
210 struct netlink_ext_ack *extack);
Alexander Aring0ac4bd62017-12-04 18:39:59 -0500211 void (*attach)(struct Qdisc *sch);
Cong Wang48bfd552018-01-25 18:26:23 -0800212 int (*change_tx_queue_len)(struct Qdisc *, unsigned int);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213
214 int (*dump)(struct Qdisc *, struct sk_buff *);
215 int (*dump_stats)(struct Qdisc *, struct gnet_dump *);
216
Jiri Pirkod47a6b02018-01-17 11:46:52 +0100217 void (*ingress_block_set)(struct Qdisc *sch,
218 u32 block_index);
219 void (*egress_block_set)(struct Qdisc *sch,
220 u32 block_index);
221 u32 (*ingress_block_get)(struct Qdisc *sch);
222 u32 (*egress_block_get)(struct Qdisc *sch);
223
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 struct module *owner;
225};
226
227
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000228struct tcf_result {
Jiri Pirkodb505142017-05-17 11:08:03 +0200229 union {
230 struct {
231 unsigned long class;
232 u32 classid;
233 };
234 const struct tcf_proto *goto_tp;
235 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236};
237
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000238struct tcf_proto_ops {
WANG Cong36272872013-12-15 20:15:11 -0800239 struct list_head head;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 char kind[IFNAMSIZ];
241
Eric Dumazetdc7f9f62011-07-05 23:25:42 +0000242 int (*classify)(struct sk_buff *,
243 const struct tcf_proto *,
244 struct tcf_result *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245 int (*init)(struct tcf_proto*);
Jakub Kicinski715df5e2018-01-24 12:54:13 -0800246 void (*destroy)(struct tcf_proto *tp,
247 struct netlink_ext_ack *extack);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248
WANG Cong8113c092017-08-04 21:31:43 -0700249 void* (*get)(struct tcf_proto*, u32 handle);
Benjamin LaHaisec1b52732013-01-14 05:15:39 +0000250 int (*change)(struct net *net, struct sk_buff *,
Eric W. Biedermanaf4c6642012-05-25 13:42:45 -0600251 struct tcf_proto*, unsigned long,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800252 u32 handle, struct nlattr **,
Alexander Aring7306db32018-01-18 11:20:51 -0500253 void **, bool,
254 struct netlink_ext_ack *);
Alexander Aring8865fdd2018-01-18 11:20:49 -0500255 int (*delete)(struct tcf_proto *tp, void *arg,
Alexander Aring571acf22018-01-18 11:20:53 -0500256 bool *last,
257 struct netlink_ext_ack *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258 void (*walk)(struct tcf_proto*, struct tcf_walker *arg);
Cong Wang07d79fc2017-08-30 14:30:36 -0700259 void (*bind_class)(void *, u32, unsigned long);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260
261 /* rtnetlink specific */
WANG Cong8113c092017-08-04 21:31:43 -0700262 int (*dump)(struct net*, struct tcf_proto*, void *,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263 struct sk_buff *skb, struct tcmsg*);
264
265 struct module *owner;
266};
267
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000268struct tcf_proto {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269 /* Fast access part */
John Fastabend25d8c0d2014-09-12 20:05:27 -0700270 struct tcf_proto __rcu *next;
271 void __rcu *root;
Eric Dumazetdc7f9f62011-07-05 23:25:42 +0000272 int (*classify)(struct sk_buff *,
273 const struct tcf_proto *,
274 struct tcf_result *);
Al Viro66c6f522006-11-20 18:07:51 -0800275 __be16 protocol;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276
277 /* All the rest */
278 u32 prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279 void *data;
Eric Dumazetdc7f9f62011-07-05 23:25:42 +0000280 const struct tcf_proto_ops *ops;
Jiri Pirko5bc17012017-05-17 11:08:01 +0200281 struct tcf_chain *chain;
John Fastabend25d8c0d2014-09-12 20:05:27 -0700282 struct rcu_head rcu;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283};
284
Jussi Kivilinna175f9c12008-07-20 00:08:47 -0700285struct qdisc_skb_cb {
286 unsigned int pkt_len;
Jiri Pirkodf4ab5b2012-07-20 02:28:49 +0000287 u16 slave_dev_queue_mapping;
Daniel Borkmann045efa82015-09-15 23:05:42 -0700288 u16 tc_classid;
Eric Dumazet25711782014-09-18 08:02:05 -0700289#define QDISC_CB_PRIV_LEN 20
290 unsigned char data[QDISC_CB_PRIV_LEN];
Jussi Kivilinna175f9c12008-07-20 00:08:47 -0700291};
292
Jiri Pirkoc7eb7d72017-11-03 11:46:24 +0100293typedef void tcf_chain_head_change_t(struct tcf_proto *tp_head, void *priv);
294
Jiri Pirko2190d1d2017-05-17 11:07:59 +0200295struct tcf_chain {
296 struct tcf_proto __rcu *filter_chain;
Jiri Pirkoa9b19442018-01-17 11:46:45 +0100297 struct list_head filter_chain_list;
Jiri Pirko5bc17012017-05-17 11:08:01 +0200298 struct list_head list;
299 struct tcf_block *block;
300 u32 index; /* chain index */
301 unsigned int refcnt;
Jiri Pirko6529eab2017-05-17 11:07:55 +0200302};
303
Jiri Pirko2190d1d2017-05-17 11:07:59 +0200304struct tcf_block {
Jiri Pirko5bc17012017-05-17 11:08:01 +0200305 struct list_head chain_list;
Jiri Pirko48617382018-01-17 11:46:46 +0100306 u32 index; /* block index for shared blocks */
307 unsigned int refcnt;
Jiri Pirko855319b2017-10-13 14:00:58 +0200308 struct net *net;
Jiri Pirko69d78ef2017-10-13 14:00:57 +0200309 struct Qdisc *q;
Jiri Pirkoacb67442017-10-19 15:50:31 +0200310 struct list_head cb_list;
Jiri Pirkof36fe1c2018-01-17 11:46:48 +0100311 struct list_head owner_list;
312 bool keep_dst;
Jiri Pirkocaa72602018-01-17 11:46:50 +0100313 unsigned int offloadcnt; /* Number of oddloaded filters */
314 unsigned int nooffloaddevcnt; /* Number of devs unable to do offload */
Jiri Pirko2190d1d2017-05-17 11:07:59 +0200315};
316
Jiri Pirkocaa72602018-01-17 11:46:50 +0100317static inline void tcf_block_offload_inc(struct tcf_block *block, u32 *flags)
318{
319 if (*flags & TCA_CLS_FLAGS_IN_HW)
320 return;
321 *flags |= TCA_CLS_FLAGS_IN_HW;
322 block->offloadcnt++;
323}
324
325static inline void tcf_block_offload_dec(struct tcf_block *block, u32 *flags)
326{
327 if (!(*flags & TCA_CLS_FLAGS_IN_HW))
328 return;
329 *flags &= ~TCA_CLS_FLAGS_IN_HW;
330 block->offloadcnt--;
331}
332
David S. Miller16bda132012-02-06 15:14:37 -0500333static inline void qdisc_cb_private_validate(const struct sk_buff *skb, int sz)
334{
335 struct qdisc_skb_cb *qcb;
Eric Dumazet5ee31c682012-06-12 06:03:51 +0000336
337 BUILD_BUG_ON(sizeof(skb->cb) < offsetof(struct qdisc_skb_cb, data) + sz);
David S. Miller16bda132012-02-06 15:14:37 -0500338 BUILD_BUG_ON(sizeof(qcb->data) < sz);
339}
340
John Fastabend7e660162017-12-07 09:57:00 -0800341static inline int qdisc_qlen_cpu(const struct Qdisc *q)
342{
343 return this_cpu_ptr(q->cpu_qstats)->qlen;
344}
345
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400346static inline int qdisc_qlen(const struct Qdisc *q)
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000347{
348 return q->q.qlen;
349}
350
John Fastabend7e660162017-12-07 09:57:00 -0800351static inline int qdisc_qlen_sum(const struct Qdisc *q)
352{
353 __u32 qlen = 0;
354 int i;
355
356 if (q->flags & TCQ_F_NOLOCK) {
357 for_each_possible_cpu(i)
358 qlen += per_cpu_ptr(q->cpu_qstats, i)->qlen;
359 } else {
360 qlen = q->q.qlen;
361 }
362
363 return qlen;
364}
365
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000366static inline struct qdisc_skb_cb *qdisc_skb_cb(const struct sk_buff *skb)
Jussi Kivilinna175f9c12008-07-20 00:08:47 -0700367{
368 return (struct qdisc_skb_cb *)skb->cb;
369}
370
David S. Miller838740002008-07-17 00:53:03 -0700371static inline spinlock_t *qdisc_lock(struct Qdisc *qdisc)
372{
373 return &qdisc->q.lock;
374}
375
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400376static inline struct Qdisc *qdisc_root(const struct Qdisc *qdisc)
David S. Miller7698b4f2008-07-16 01:42:40 -0700377{
John Fastabend46e5da40a2014-09-12 20:04:52 -0700378 struct Qdisc *q = rcu_dereference_rtnl(qdisc->dev_queue->qdisc);
379
380 return q;
David S. Miller7698b4f2008-07-16 01:42:40 -0700381}
382
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400383static inline struct Qdisc *qdisc_root_sleeping(const struct Qdisc *qdisc)
Jarek Poplawski2540e052008-08-21 05:11:14 -0700384{
385 return qdisc->dev_queue->qdisc_sleeping;
386}
387
David S. Miller7e43f112008-08-02 23:27:37 -0700388/* The qdisc root lock is a mechanism by which to top level
389 * of a qdisc tree can be locked from any qdisc node in the
390 * forest. This allows changing the configuration of some
391 * aspect of the qdisc tree while blocking out asynchronous
392 * qdisc access in the packet processing paths.
393 *
394 * It is only legal to do this when the root will not change
395 * on us. Otherwise we'll potentially lock the wrong qdisc
396 * root. This is enforced by holding the RTNL semaphore, which
397 * all users of this lock accessor must do.
398 */
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400399static inline spinlock_t *qdisc_root_lock(const struct Qdisc *qdisc)
David S. Miller7698b4f2008-07-16 01:42:40 -0700400{
401 struct Qdisc *root = qdisc_root(qdisc);
402
David S. Miller7e43f112008-08-02 23:27:37 -0700403 ASSERT_RTNL();
David S. Miller838740002008-07-17 00:53:03 -0700404 return qdisc_lock(root);
David S. Miller7698b4f2008-07-16 01:42:40 -0700405}
406
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400407static inline spinlock_t *qdisc_root_sleeping_lock(const struct Qdisc *qdisc)
Jarek Poplawskif6f9b932008-08-27 02:25:17 -0700408{
409 struct Qdisc *root = qdisc_root_sleeping(qdisc);
410
411 ASSERT_RTNL();
412 return qdisc_lock(root);
413}
414
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700415static inline seqcount_t *qdisc_root_sleeping_running(const struct Qdisc *qdisc)
416{
417 struct Qdisc *root = qdisc_root_sleeping(qdisc);
418
419 ASSERT_RTNL();
420 return &root->running;
421}
422
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400423static inline struct net_device *qdisc_dev(const struct Qdisc *qdisc)
David S. Miller5ce2d482008-07-08 17:06:30 -0700424{
425 return qdisc->dev_queue->dev;
426}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400428static inline void sch_tree_lock(const struct Qdisc *q)
David S. Miller78a5b302008-07-16 03:12:24 -0700429{
Jarek Poplawskife439dd2008-08-27 02:27:10 -0700430 spin_lock_bh(qdisc_root_sleeping_lock(q));
David S. Miller78a5b302008-07-16 03:12:24 -0700431}
432
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400433static inline void sch_tree_unlock(const struct Qdisc *q)
David S. Miller78a5b302008-07-16 03:12:24 -0700434{
Jarek Poplawskife439dd2008-08-27 02:27:10 -0700435 spin_unlock_bh(qdisc_root_sleeping_lock(q));
David S. Miller78a5b302008-07-16 03:12:24 -0700436}
437
Thomas Grafe41a33e2005-07-05 14:14:30 -0700438extern struct Qdisc noop_qdisc;
439extern struct Qdisc_ops noop_qdisc_ops;
David S. Miller6ec1c692009-09-06 01:58:51 -0700440extern struct Qdisc_ops pfifo_fast_ops;
441extern struct Qdisc_ops mq_qdisc_ops;
Phil Sutterd66d6c32015-08-27 21:21:38 +0200442extern struct Qdisc_ops noqueue_qdisc_ops;
stephen hemminger6da7c8f2013-08-27 16:19:08 -0700443extern const struct Qdisc_ops *default_qdisc_ops;
Eric Dumazet1f27cde2016-03-02 08:21:43 -0800444static inline const struct Qdisc_ops *
445get_default_qdisc_ops(const struct net_device *dev, int ntx)
446{
447 return ntx < dev->real_num_tx_queues ?
448 default_qdisc_ops : &pfifo_fast_ops;
449}
Thomas Grafe41a33e2005-07-05 14:14:30 -0700450
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000451struct Qdisc_class_common {
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700452 u32 classid;
453 struct hlist_node hnode;
454};
455
Eric Dumazetfd2c3ef2009-11-03 03:26:03 +0000456struct Qdisc_class_hash {
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700457 struct hlist_head *hash;
458 unsigned int hashsize;
459 unsigned int hashmask;
460 unsigned int hashelems;
461};
462
463static inline unsigned int qdisc_class_hash(u32 id, u32 mask)
464{
465 id ^= id >> 8;
466 id ^= id >> 4;
467 return id & mask;
468}
469
470static inline struct Qdisc_class_common *
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400471qdisc_class_find(const struct Qdisc_class_hash *hash, u32 id)
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700472{
473 struct Qdisc_class_common *cl;
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700474 unsigned int h;
475
Gao Feng7d3f0cd2017-08-18 15:23:24 +0800476 if (!id)
477 return NULL;
478
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700479 h = qdisc_class_hash(id, hash->hashmask);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800480 hlist_for_each_entry(cl, &hash->hash[h], hnode) {
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700481 if (cl->classid == id)
482 return cl;
483 }
484 return NULL;
485}
486
Amritha Nambiar384c1812017-10-27 02:35:34 -0700487static inline int tc_classid_to_hwtc(struct net_device *dev, u32 classid)
488{
489 u32 hwtc = TC_H_MIN(classid) - TC_H_MIN_PRIORITY;
490
491 return (hwtc < netdev_get_num_tc(dev)) ? hwtc : -EINVAL;
492}
493
Joe Perches5c152572013-07-30 22:47:13 -0700494int qdisc_class_hash_init(struct Qdisc_class_hash *);
495void qdisc_class_hash_insert(struct Qdisc_class_hash *,
496 struct Qdisc_class_common *);
497void qdisc_class_hash_remove(struct Qdisc_class_hash *,
498 struct Qdisc_class_common *);
499void qdisc_class_hash_grow(struct Qdisc *, struct Qdisc_class_hash *);
500void qdisc_class_hash_destroy(struct Qdisc_class_hash *);
Patrick McHardy6fe1c7a2008-07-05 23:21:31 -0700501
Cong Wang48bfd552018-01-25 18:26:23 -0800502int dev_qdisc_change_tx_queue_len(struct net_device *dev);
Joe Perches5c152572013-07-30 22:47:13 -0700503void dev_init_scheduler(struct net_device *dev);
504void dev_shutdown(struct net_device *dev);
505void dev_activate(struct net_device *dev);
506void dev_deactivate(struct net_device *dev);
507void dev_deactivate_many(struct list_head *head);
508struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
509 struct Qdisc *qdisc);
510void qdisc_reset(struct Qdisc *qdisc);
511void qdisc_destroy(struct Qdisc *qdisc);
WANG Cong2ccccf52016-02-25 14:55:01 -0800512void qdisc_tree_reduce_backlog(struct Qdisc *qdisc, unsigned int n,
513 unsigned int len);
Joe Perches5c152572013-07-30 22:47:13 -0700514struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
Alexander Aringd0bd6842017-12-20 12:35:20 -0500515 const struct Qdisc_ops *ops,
516 struct netlink_ext_ack *extack);
Daniel Borkmann81d947e2018-01-15 23:12:09 +0100517void qdisc_free(struct Qdisc *qdisc);
Joe Perches5c152572013-07-30 22:47:13 -0700518struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue,
Alexander Aringa38a98822017-12-20 12:35:21 -0500519 const struct Qdisc_ops *ops, u32 parentid,
520 struct netlink_ext_ack *extack);
Joe Perches5c152572013-07-30 22:47:13 -0700521void __qdisc_calculate_pkt_len(struct sk_buff *skb,
522 const struct qdisc_size_table *stab);
Alexei Starovoitov27b29f62015-09-15 23:05:43 -0700523int skb_do_redirect(struct sk_buff *);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524
Willem de Bruijna5135bc2017-01-07 17:06:36 -0500525static inline void skb_reset_tc(struct sk_buff *skb)
526{
527#ifdef CONFIG_NET_CLS_ACT
Willem de Bruijnbc31c902017-01-07 17:06:38 -0500528 skb->tc_redirected = 0;
Willem de Bruijna5135bc2017-01-07 17:06:36 -0500529#endif
530}
531
Daniel Borkmannfdc54322016-01-07 15:50:22 +0100532static inline bool skb_at_tc_ingress(const struct sk_buff *skb)
533{
534#ifdef CONFIG_NET_CLS_ACT
Willem de Bruijn8dc07fd2017-01-07 17:06:37 -0500535 return skb->tc_at_ingress;
Daniel Borkmannfdc54322016-01-07 15:50:22 +0100536#else
537 return false;
538#endif
539}
540
Willem de Bruijne7246e12017-01-07 17:06:35 -0500541static inline bool skb_skip_tc_classify(struct sk_buff *skb)
542{
543#ifdef CONFIG_NET_CLS_ACT
544 if (skb->tc_skip_classify) {
545 skb->tc_skip_classify = 0;
546 return true;
547 }
548#endif
549 return false;
550}
551
Gal Pressman3a053b12018-02-28 15:59:15 +0200552/* Reset all TX qdiscs greater than index of a device. */
John Fastabendf0796d52010-07-01 13:21:57 +0000553static inline void qdisc_reset_all_tx_gt(struct net_device *dev, unsigned int i)
David S. Miller5aa70992008-07-08 22:59:10 -0700554{
John Fastabend4ef6acf2010-07-01 13:21:35 +0000555 struct Qdisc *qdisc;
556
John Fastabendf0796d52010-07-01 13:21:57 +0000557 for (; i < dev->num_tx_queues; i++) {
John Fastabend46e5da40a2014-09-12 20:04:52 -0700558 qdisc = rtnl_dereference(netdev_get_tx_queue(dev, i)->qdisc);
John Fastabend4ef6acf2010-07-01 13:21:35 +0000559 if (qdisc) {
560 spin_lock_bh(qdisc_lock(qdisc));
561 qdisc_reset(qdisc);
562 spin_unlock_bh(qdisc_lock(qdisc));
563 }
564 }
David S. Miller5aa70992008-07-08 22:59:10 -0700565}
566
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567static inline void qdisc_reset_all_tx(struct net_device *dev)
Thomas Graf9972b252005-06-18 22:57:26 -0700568{
John Fastabendf0796d52010-07-01 13:21:57 +0000569 qdisc_reset_all_tx_gt(dev, 0);
Thomas Graf9972b252005-06-18 22:57:26 -0700570}
571
David S. Miller3e745dd2008-07-08 23:00:25 -0700572/* Are all TX queues of the device empty? */
573static inline bool qdisc_all_tx_empty(const struct net_device *dev)
574{
David S. Millere8a04642008-07-17 00:34:19 -0700575 unsigned int i;
John Fastabend46e5da40a2014-09-12 20:04:52 -0700576
577 rcu_read_lock();
David S. Millere8a04642008-07-17 00:34:19 -0700578 for (i = 0; i < dev->num_tx_queues; i++) {
579 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
John Fastabend46e5da40a2014-09-12 20:04:52 -0700580 const struct Qdisc *q = rcu_dereference(txq->qdisc);
David S. Miller3e745dd2008-07-08 23:00:25 -0700581
John Fastabend46e5da40a2014-09-12 20:04:52 -0700582 if (q->q.qlen) {
583 rcu_read_unlock();
David S. Millere8a04642008-07-17 00:34:19 -0700584 return false;
John Fastabend46e5da40a2014-09-12 20:04:52 -0700585 }
David S. Millere8a04642008-07-17 00:34:19 -0700586 }
John Fastabend46e5da40a2014-09-12 20:04:52 -0700587 rcu_read_unlock();
David S. Millere8a04642008-07-17 00:34:19 -0700588 return true;
David S. Miller3e745dd2008-07-08 23:00:25 -0700589}
590
David S. Miller6fa98642008-07-08 23:01:06 -0700591/* Are any of the TX qdiscs changing? */
Eric Dumazet05bdd2f2011-10-20 17:45:43 -0400592static inline bool qdisc_tx_changing(const struct net_device *dev)
David S. Miller6fa98642008-07-08 23:01:06 -0700593{
David S. Millere8a04642008-07-17 00:34:19 -0700594 unsigned int i;
John Fastabend46e5da40a2014-09-12 20:04:52 -0700595
David S. Millere8a04642008-07-17 00:34:19 -0700596 for (i = 0; i < dev->num_tx_queues; i++) {
597 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
John Fastabend46e5da40a2014-09-12 20:04:52 -0700598 if (rcu_access_pointer(txq->qdisc) != txq->qdisc_sleeping)
David S. Millere8a04642008-07-17 00:34:19 -0700599 return true;
600 }
601 return false;
David S. Miller6fa98642008-07-08 23:01:06 -0700602}
603
David S. Millere8a04642008-07-17 00:34:19 -0700604/* Is the device using the noop qdisc on all queues? */
David S. Miller05297942008-07-08 23:01:27 -0700605static inline bool qdisc_tx_is_noop(const struct net_device *dev)
606{
David S. Millere8a04642008-07-17 00:34:19 -0700607 unsigned int i;
John Fastabend46e5da40a2014-09-12 20:04:52 -0700608
David S. Millere8a04642008-07-17 00:34:19 -0700609 for (i = 0; i < dev->num_tx_queues; i++) {
610 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
John Fastabend46e5da40a2014-09-12 20:04:52 -0700611 if (rcu_access_pointer(txq->qdisc) != &noop_qdisc)
David S. Millere8a04642008-07-17 00:34:19 -0700612 return false;
613 }
614 return true;
David S. Miller05297942008-07-08 23:01:27 -0700615}
616
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000617static inline unsigned int qdisc_pkt_len(const struct sk_buff *skb)
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700618{
Jussi Kivilinna175f9c12008-07-20 00:08:47 -0700619 return qdisc_skb_cb(skb)->pkt_len;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700620}
621
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700622/* additional qdisc xmit flags (NET_XMIT_MASK in linux/netdevice.h) */
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700623enum net_xmit_qdisc_t {
624 __NET_XMIT_STOLEN = 0x00010000,
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700625 __NET_XMIT_BYPASS = 0x00020000,
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700626};
627
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700628#ifdef CONFIG_NET_CLS_ACT
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700629#define net_xmit_drop_count(e) ((e) & __NET_XMIT_STOLEN ? 0 : 1)
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700630#else
631#define net_xmit_drop_count(e) (1)
632#endif
633
Eric Dumazeta2da5702011-01-20 03:48:19 +0000634static inline void qdisc_calculate_pkt_len(struct sk_buff *skb,
635 const struct Qdisc *sch)
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700636{
David S. Miller3a682fb2008-07-20 18:13:01 -0700637#ifdef CONFIG_NET_SCHED
Eric Dumazeta2da5702011-01-20 03:48:19 +0000638 struct qdisc_size_table *stab = rcu_dereference_bh(sch->stab);
639
640 if (stab)
641 __qdisc_calculate_pkt_len(skb, stab);
David S. Miller3a682fb2008-07-20 18:13:01 -0700642#endif
Eric Dumazeta2da5702011-01-20 03:48:19 +0000643}
644
Eric Dumazet520ac302016-06-21 23:16:49 -0700645static inline int qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
646 struct sk_buff **to_free)
Eric Dumazeta2da5702011-01-20 03:48:19 +0000647{
648 qdisc_calculate_pkt_len(skb, sch);
Eric Dumazet520ac302016-06-21 23:16:49 -0700649 return sch->enqueue(skb, sch, to_free);
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700650}
651
John Fastabend22e0f8b2014-09-28 11:52:56 -0700652static inline bool qdisc_is_percpu_stats(const struct Qdisc *q)
653{
654 return q->flags & TCQ_F_CPUSTATS;
655}
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000656
Amir Vadai38040702016-05-13 12:55:35 +0000657static inline void _bstats_update(struct gnet_stats_basic_packed *bstats,
658 __u64 bytes, __u32 packets)
659{
660 bstats->bytes += bytes;
661 bstats->packets += packets;
662}
663
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000664static inline void bstats_update(struct gnet_stats_basic_packed *bstats,
665 const struct sk_buff *skb)
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000666{
Amir Vadai38040702016-05-13 12:55:35 +0000667 _bstats_update(bstats,
668 qdisc_pkt_len(skb),
669 skb_is_gso(skb) ? skb_shinfo(skb)->gso_segs : 1);
670}
671
672static inline void _bstats_cpu_update(struct gnet_stats_basic_cpu *bstats,
673 __u64 bytes, __u32 packets)
674{
675 u64_stats_update_begin(&bstats->syncp);
676 _bstats_update(&bstats->bstats, bytes, packets);
677 u64_stats_update_end(&bstats->syncp);
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000678}
679
Eric Dumazet24ea5912015-07-06 05:18:03 -0700680static inline void bstats_cpu_update(struct gnet_stats_basic_cpu *bstats,
681 const struct sk_buff *skb)
John Fastabend22e0f8b2014-09-28 11:52:56 -0700682{
John Fastabend22e0f8b2014-09-28 11:52:56 -0700683 u64_stats_update_begin(&bstats->syncp);
684 bstats_update(&bstats->bstats, skb);
685 u64_stats_update_end(&bstats->syncp);
686}
687
Eric Dumazet24ea5912015-07-06 05:18:03 -0700688static inline void qdisc_bstats_cpu_update(struct Qdisc *sch,
689 const struct sk_buff *skb)
690{
691 bstats_cpu_update(this_cpu_ptr(sch->cpu_bstats), skb);
692}
693
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000694static inline void qdisc_bstats_update(struct Qdisc *sch,
695 const struct sk_buff *skb)
696{
697 bstats_update(&sch->bstats, skb);
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000698}
699
John Fastabend25331d62014-09-28 11:53:29 -0700700static inline void qdisc_qstats_backlog_dec(struct Qdisc *sch,
701 const struct sk_buff *skb)
702{
703 sch->qstats.backlog -= qdisc_pkt_len(skb);
704}
705
John Fastabend40bd0362017-12-07 09:55:07 -0800706static inline void qdisc_qstats_cpu_backlog_dec(struct Qdisc *sch,
707 const struct sk_buff *skb)
708{
709 this_cpu_sub(sch->cpu_qstats->backlog, qdisc_pkt_len(skb));
710}
711
John Fastabend25331d62014-09-28 11:53:29 -0700712static inline void qdisc_qstats_backlog_inc(struct Qdisc *sch,
713 const struct sk_buff *skb)
714{
715 sch->qstats.backlog += qdisc_pkt_len(skb);
716}
717
John Fastabend40bd0362017-12-07 09:55:07 -0800718static inline void qdisc_qstats_cpu_backlog_inc(struct Qdisc *sch,
719 const struct sk_buff *skb)
720{
721 this_cpu_add(sch->cpu_qstats->backlog, qdisc_pkt_len(skb));
722}
723
724static inline void qdisc_qstats_cpu_qlen_inc(struct Qdisc *sch)
725{
726 this_cpu_inc(sch->cpu_qstats->qlen);
727}
728
729static inline void qdisc_qstats_cpu_qlen_dec(struct Qdisc *sch)
730{
731 this_cpu_dec(sch->cpu_qstats->qlen);
732}
733
734static inline void qdisc_qstats_cpu_requeues_inc(struct Qdisc *sch)
735{
736 this_cpu_inc(sch->cpu_qstats->requeues);
737}
738
John Fastabend25331d62014-09-28 11:53:29 -0700739static inline void __qdisc_qstats_drop(struct Qdisc *sch, int count)
740{
741 sch->qstats.drops += count;
742}
743
Eric Dumazet24ea5912015-07-06 05:18:03 -0700744static inline void qstats_drop_inc(struct gnet_stats_queue *qstats)
John Fastabend25331d62014-09-28 11:53:29 -0700745{
Eric Dumazet24ea5912015-07-06 05:18:03 -0700746 qstats->drops++;
John Fastabend25331d62014-09-28 11:53:29 -0700747}
748
Eric Dumazet24ea5912015-07-06 05:18:03 -0700749static inline void qstats_overlimit_inc(struct gnet_stats_queue *qstats)
John Fastabendb0ab6f92014-09-28 11:54:24 -0700750{
Eric Dumazet24ea5912015-07-06 05:18:03 -0700751 qstats->overlimits++;
752}
John Fastabendb0ab6f92014-09-28 11:54:24 -0700753
Eric Dumazet24ea5912015-07-06 05:18:03 -0700754static inline void qdisc_qstats_drop(struct Qdisc *sch)
755{
756 qstats_drop_inc(&sch->qstats);
757}
758
759static inline void qdisc_qstats_cpu_drop(struct Qdisc *sch)
760{
Eric Dumazeteb60a8d2016-08-24 10:23:34 -0700761 this_cpu_inc(sch->cpu_qstats->drops);
John Fastabendb0ab6f92014-09-28 11:54:24 -0700762}
763
John Fastabend25331d62014-09-28 11:53:29 -0700764static inline void qdisc_qstats_overlimit(struct Qdisc *sch)
765{
766 sch->qstats.overlimits++;
767}
768
Florian Westphal48da34b2016-09-18 00:57:34 +0200769static inline void qdisc_skb_head_init(struct qdisc_skb_head *qh)
Thomas Graf9972b252005-06-18 22:57:26 -0700770{
Florian Westphal48da34b2016-09-18 00:57:34 +0200771 qh->head = NULL;
772 qh->tail = NULL;
773 qh->qlen = 0;
774}
775
776static inline int __qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch,
777 struct qdisc_skb_head *qh)
778{
779 struct sk_buff *last = qh->tail;
780
781 if (last) {
782 skb->next = NULL;
783 last->next = skb;
784 qh->tail = skb;
785 } else {
786 qh->tail = skb;
787 qh->head = skb;
788 }
789 qh->qlen++;
John Fastabend25331d62014-09-28 11:53:29 -0700790 qdisc_qstats_backlog_inc(sch, skb);
Thomas Graf9972b252005-06-18 22:57:26 -0700791
792 return NET_XMIT_SUCCESS;
793}
794
795static inline int qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch)
796{
797 return __qdisc_enqueue_tail(skb, sch, &sch->q);
798}
799
Florian Westphal48da34b2016-09-18 00:57:34 +0200800static inline struct sk_buff *__qdisc_dequeue_head(struct qdisc_skb_head *qh)
Thomas Graf9972b252005-06-18 22:57:26 -0700801{
Florian Westphal48da34b2016-09-18 00:57:34 +0200802 struct sk_buff *skb = qh->head;
803
804 if (likely(skb != NULL)) {
805 qh->head = skb->next;
806 qh->qlen--;
807 if (qh->head == NULL)
808 qh->tail = NULL;
809 skb->next = NULL;
810 }
Thomas Graf9972b252005-06-18 22:57:26 -0700811
Florian Westphalec323362016-09-18 00:57:32 +0200812 return skb;
813}
814
815static inline struct sk_buff *qdisc_dequeue_head(struct Qdisc *sch)
816{
817 struct sk_buff *skb = __qdisc_dequeue_head(&sch->q);
818
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800819 if (likely(skb != NULL)) {
John Fastabend25331d62014-09-28 11:53:29 -0700820 qdisc_qstats_backlog_dec(sch, skb);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800821 qdisc_bstats_update(sch, skb);
822 }
Thomas Graf9972b252005-06-18 22:57:26 -0700823
824 return skb;
825}
826
Eric Dumazet520ac302016-06-21 23:16:49 -0700827/* Instead of calling kfree_skb() while root qdisc lock is held,
828 * queue the skb for future freeing at end of __dev_xmit_skb()
829 */
830static inline void __qdisc_drop(struct sk_buff *skb, struct sk_buff **to_free)
831{
832 skb->next = *to_free;
833 *to_free = skb;
834}
835
Alexey Kodanev35d889d2018-03-05 20:52:54 +0300836static inline void __qdisc_drop_all(struct sk_buff *skb,
837 struct sk_buff **to_free)
838{
839 if (skb->prev)
840 skb->prev->next = *to_free;
841 else
842 skb->next = *to_free;
843 *to_free = skb;
844}
845
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000846static inline unsigned int __qdisc_queue_drop_head(struct Qdisc *sch,
Florian Westphal48da34b2016-09-18 00:57:34 +0200847 struct qdisc_skb_head *qh,
Eric Dumazet520ac302016-06-21 23:16:49 -0700848 struct sk_buff **to_free)
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000849{
Florian Westphal48da34b2016-09-18 00:57:34 +0200850 struct sk_buff *skb = __qdisc_dequeue_head(qh);
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000851
852 if (likely(skb != NULL)) {
853 unsigned int len = qdisc_pkt_len(skb);
Eric Dumazet520ac302016-06-21 23:16:49 -0700854
John Fastabend25331d62014-09-28 11:53:29 -0700855 qdisc_qstats_backlog_dec(sch, skb);
Eric Dumazet520ac302016-06-21 23:16:49 -0700856 __qdisc_drop(skb, to_free);
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000857 return len;
858 }
859
860 return 0;
861}
862
Eric Dumazet520ac302016-06-21 23:16:49 -0700863static inline unsigned int qdisc_queue_drop_head(struct Qdisc *sch,
864 struct sk_buff **to_free)
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000865{
Eric Dumazet520ac302016-06-21 23:16:49 -0700866 return __qdisc_queue_drop_head(sch, &sch->q, to_free);
Hagen Paul Pfeifer57dbb2d2010-01-24 12:30:59 +0000867}
868
Patrick McHardy48a8f512008-10-31 00:44:18 -0700869static inline struct sk_buff *qdisc_peek_head(struct Qdisc *sch)
870{
Florian Westphal48da34b2016-09-18 00:57:34 +0200871 const struct qdisc_skb_head *qh = &sch->q;
872
873 return qh->head;
Patrick McHardy48a8f512008-10-31 00:44:18 -0700874}
875
Jarek Poplawski77be1552008-10-31 00:47:01 -0700876/* generic pseudo peek method for non-work-conserving qdisc */
877static inline struct sk_buff *qdisc_peek_dequeued(struct Qdisc *sch)
878{
John Fastabenda53851e2017-12-07 09:55:45 -0800879 struct sk_buff *skb = skb_peek(&sch->gso_skb);
880
Jarek Poplawski77be1552008-10-31 00:47:01 -0700881 /* we can reuse ->gso_skb because peek isn't called for root qdiscs */
John Fastabenda53851e2017-12-07 09:55:45 -0800882 if (!skb) {
883 skb = sch->dequeue(sch);
884
885 if (skb) {
886 __skb_queue_head(&sch->gso_skb, skb);
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800887 /* it's still part of the queue */
John Fastabenda53851e2017-12-07 09:55:45 -0800888 qdisc_qstats_backlog_inc(sch, skb);
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800889 sch->q.qlen++;
WANG Conga27758f2016-06-03 15:05:57 -0700890 }
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800891 }
Jarek Poplawski77be1552008-10-31 00:47:01 -0700892
John Fastabenda53851e2017-12-07 09:55:45 -0800893 return skb;
Jarek Poplawski77be1552008-10-31 00:47:01 -0700894}
895
896/* use instead of qdisc->dequeue() for all qdiscs queried with ->peek() */
897static inline struct sk_buff *qdisc_dequeue_peeked(struct Qdisc *sch)
898{
John Fastabenda53851e2017-12-07 09:55:45 -0800899 struct sk_buff *skb = skb_peek(&sch->gso_skb);
Jarek Poplawski77be1552008-10-31 00:47:01 -0700900
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800901 if (skb) {
John Fastabenda53851e2017-12-07 09:55:45 -0800902 skb = __skb_dequeue(&sch->gso_skb);
WANG Conga27758f2016-06-03 15:05:57 -0700903 qdisc_qstats_backlog_dec(sch, skb);
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800904 sch->q.qlen--;
905 } else {
Jarek Poplawski77be1552008-10-31 00:47:01 -0700906 skb = sch->dequeue(sch);
Jarek Poplawski61c9eaf2008-11-05 16:02:34 -0800907 }
Jarek Poplawski77be1552008-10-31 00:47:01 -0700908
909 return skb;
910}
911
Florian Westphal48da34b2016-09-18 00:57:34 +0200912static inline void __qdisc_reset_queue(struct qdisc_skb_head *qh)
Thomas Graf9972b252005-06-18 22:57:26 -0700913{
914 /*
915 * We do not know the backlog in bytes of this list, it
916 * is up to the caller to correct it
917 */
Florian Westphal48da34b2016-09-18 00:57:34 +0200918 ASSERT_RTNL();
919 if (qh->qlen) {
920 rtnl_kfree_skbs(qh->head, qh->tail);
921
922 qh->head = NULL;
923 qh->tail = NULL;
924 qh->qlen = 0;
Eric Dumazet1b5c5492016-06-13 20:21:50 -0700925 }
Thomas Graf9972b252005-06-18 22:57:26 -0700926}
927
928static inline void qdisc_reset_queue(struct Qdisc *sch)
929{
Eric Dumazet1b5c5492016-06-13 20:21:50 -0700930 __qdisc_reset_queue(&sch->q);
Thomas Graf9972b252005-06-18 22:57:26 -0700931 sch->qstats.backlog = 0;
932}
933
WANG Cong86a79962016-02-25 14:55:00 -0800934static inline struct Qdisc *qdisc_replace(struct Qdisc *sch, struct Qdisc *new,
935 struct Qdisc **pold)
936{
937 struct Qdisc *old;
938
939 sch_tree_lock(sch);
940 old = *pold;
941 *pold = new;
942 if (old != NULL) {
Konstantin Khlebnikov68a66d12017-08-19 15:37:07 +0300943 unsigned int qlen = old->q.qlen;
944 unsigned int backlog = old->qstats.backlog;
945
WANG Cong86a79962016-02-25 14:55:00 -0800946 qdisc_reset(old);
Konstantin Khlebnikov68a66d12017-08-19 15:37:07 +0300947 qdisc_tree_reduce_backlog(old, qlen, backlog);
WANG Cong86a79962016-02-25 14:55:00 -0800948 }
949 sch_tree_unlock(sch);
950
951 return old;
952}
953
Eric Dumazet1b5c5492016-06-13 20:21:50 -0700954static inline void rtnl_qdisc_drop(struct sk_buff *skb, struct Qdisc *sch)
955{
956 rtnl_kfree_skbs(skb, skb);
957 qdisc_qstats_drop(sch);
958}
959
John Fastabend40bd0362017-12-07 09:55:07 -0800960static inline int qdisc_drop_cpu(struct sk_buff *skb, struct Qdisc *sch,
961 struct sk_buff **to_free)
962{
963 __qdisc_drop(skb, to_free);
964 qdisc_qstats_cpu_drop(sch);
965
966 return NET_XMIT_DROP;
967}
Eric Dumazet520ac302016-06-21 23:16:49 -0700968
969static inline int qdisc_drop(struct sk_buff *skb, struct Qdisc *sch,
970 struct sk_buff **to_free)
Thomas Graf9972b252005-06-18 22:57:26 -0700971{
Eric Dumazet520ac302016-06-21 23:16:49 -0700972 __qdisc_drop(skb, to_free);
John Fastabend25331d62014-09-28 11:53:29 -0700973 qdisc_qstats_drop(sch);
Thomas Graf9972b252005-06-18 22:57:26 -0700974
975 return NET_XMIT_DROP;
976}
977
Alexey Kodanev35d889d2018-03-05 20:52:54 +0300978static inline int qdisc_drop_all(struct sk_buff *skb, struct Qdisc *sch,
979 struct sk_buff **to_free)
980{
981 __qdisc_drop_all(skb, to_free);
982 qdisc_qstats_drop(sch);
983
984 return NET_XMIT_DROP;
985}
986
Jesper Dangaard Brouere9bef552007-09-12 16:35:24 +0200987/* Length to Time (L2T) lookup in a qdisc_rate_table, to determine how
988 long it will take to send a packet given its size.
989 */
990static inline u32 qdisc_l2t(struct qdisc_rate_table* rtab, unsigned int pktlen)
991{
Jesper Dangaard Brouere08b0992007-09-12 16:36:28 +0200992 int slot = pktlen + rtab->rate.cell_align + rtab->rate.overhead;
993 if (slot < 0)
994 slot = 0;
Jesper Dangaard Brouere9bef552007-09-12 16:35:24 +0200995 slot >>= rtab->rate.cell_log;
996 if (slot > 255)
Eric Dumazeta02cec22010-09-22 20:43:57 +0000997 return rtab->data[255]*(slot >> 8) + rtab->data[slot & 0xFF];
Jesper Dangaard Brouere9bef552007-09-12 16:35:24 +0200998 return rtab->data[slot];
999}
1000
Jiri Pirko292f1c72013-02-12 00:12:03 +00001001struct psched_ratecfg {
Eric Dumazet130d3d62013-06-06 13:56:19 -07001002 u64 rate_bytes_ps; /* bytes per second */
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001003 u32 mult;
1004 u16 overhead;
Jesper Dangaard Brouer8a8e3d82013-08-14 23:47:11 +02001005 u8 linklayer;
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001006 u8 shift;
Jiri Pirko292f1c72013-02-12 00:12:03 +00001007};
1008
1009static inline u64 psched_l2t_ns(const struct psched_ratecfg *r,
1010 unsigned int len)
1011{
Jesper Dangaard Brouer8a8e3d82013-08-14 23:47:11 +02001012 len += r->overhead;
1013
1014 if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
1015 return ((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift;
1016
1017 return ((u64)len * r->mult) >> r->shift;
Jiri Pirko292f1c72013-02-12 00:12:03 +00001018}
1019
Joe Perches5c152572013-07-30 22:47:13 -07001020void psched_ratecfg_precompute(struct psched_ratecfg *r,
Eric Dumazet3e1e3aa2013-09-19 09:10:03 -07001021 const struct tc_ratespec *conf,
1022 u64 rate64);
Jiri Pirko292f1c72013-02-12 00:12:03 +00001023
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001024static inline void psched_ratecfg_getrate(struct tc_ratespec *res,
1025 const struct psched_ratecfg *r)
Jiri Pirko292f1c72013-02-12 00:12:03 +00001026{
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001027 memset(res, 0, sizeof(*res));
Eric Dumazet3e1e3aa2013-09-19 09:10:03 -07001028
1029 /* legacy struct tc_ratespec has a 32bit @rate field
1030 * Qdisc using 64bit rate should add new attributes
1031 * in order to maintain compatibility.
1032 */
1033 res->rate = min_t(u64, r->rate_bytes_ps, ~0U);
1034
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001035 res->overhead = r->overhead;
Jesper Dangaard Brouer8a8e3d82013-08-14 23:47:11 +02001036 res->linklayer = (r->linklayer & TC_LINKLAYER_MASK);
Jiri Pirko292f1c72013-02-12 00:12:03 +00001037}
1038
Jiri Pirko46209402017-11-03 11:46:25 +01001039/* Mini Qdisc serves for specific needs of ingress/clsact Qdisc.
1040 * The fast path only needs to access filter list and to update stats
1041 */
1042struct mini_Qdisc {
1043 struct tcf_proto *filter_list;
1044 struct gnet_stats_basic_cpu __percpu *cpu_bstats;
1045 struct gnet_stats_queue __percpu *cpu_qstats;
1046 struct rcu_head rcu;
1047};
1048
1049static inline void mini_qdisc_bstats_cpu_update(struct mini_Qdisc *miniq,
1050 const struct sk_buff *skb)
1051{
1052 bstats_cpu_update(this_cpu_ptr(miniq->cpu_bstats), skb);
1053}
1054
1055static inline void mini_qdisc_qstats_cpu_drop(struct mini_Qdisc *miniq)
1056{
1057 this_cpu_inc(miniq->cpu_qstats->drops);
1058}
1059
1060struct mini_Qdisc_pair {
1061 struct mini_Qdisc miniq1;
1062 struct mini_Qdisc miniq2;
1063 struct mini_Qdisc __rcu **p_miniq;
1064};
1065
1066void mini_qdisc_pair_swap(struct mini_Qdisc_pair *miniqp,
1067 struct tcf_proto *tp_head);
1068void mini_qdisc_pair_init(struct mini_Qdisc_pair *miniqp, struct Qdisc *qdisc,
1069 struct mini_Qdisc __rcu **p_miniq);
1070
Linus Torvalds1da177e2005-04-16 15:20:36 -07001071#endif