xref: /openbmc/linux/include/net/sch_generic.h (revision bd329f028f1cd51c7623c326147af07c6d832193)
1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef __NET_SCHED_GENERIC_H
3 #define __NET_SCHED_GENERIC_H
4 
5 #include <linux/netdevice.h>
6 #include <linux/types.h>
7 #include <linux/rcupdate.h>
8 #include <linux/pkt_sched.h>
9 #include <linux/pkt_cls.h>
10 #include <linux/percpu.h>
11 #include <linux/dynamic_queue_limits.h>
12 #include <linux/list.h>
13 #include <linux/refcount.h>
14 #include <linux/workqueue.h>
15 #include <net/gen_stats.h>
16 #include <net/rtnetlink.h>
17 
18 struct Qdisc_ops;
19 struct qdisc_walker;
20 struct tcf_walker;
21 struct module;
22 
23 struct qdisc_rate_table {
24 	struct tc_ratespec rate;
25 	u32		data[256];
26 	struct qdisc_rate_table *next;
27 	int		refcnt;
28 };
29 
30 enum qdisc_state_t {
31 	__QDISC_STATE_SCHED,
32 	__QDISC_STATE_DEACTIVATED,
33 };
34 
35 struct qdisc_size_table {
36 	struct rcu_head		rcu;
37 	struct list_head	list;
38 	struct tc_sizespec	szopts;
39 	int			refcnt;
40 	u16			data[];
41 };
42 
43 /* similar to sk_buff_head, but skb->prev pointer is undefined. */
44 struct qdisc_skb_head {
45 	struct sk_buff	*head;
46 	struct sk_buff	*tail;
47 	__u32		qlen;
48 	spinlock_t	lock;
49 };
50 
51 struct Qdisc {
52 	int 			(*enqueue)(struct sk_buff *skb,
53 					   struct Qdisc *sch,
54 					   struct sk_buff **to_free);
55 	struct sk_buff *	(*dequeue)(struct Qdisc *sch);
56 	unsigned int		flags;
57 #define TCQ_F_BUILTIN		1
58 #define TCQ_F_INGRESS		2
59 #define TCQ_F_CAN_BYPASS	4
60 #define TCQ_F_MQROOT		8
61 #define TCQ_F_ONETXQUEUE	0x10 /* dequeue_skb() can assume all skbs are for
62 				      * q->dev_queue : It can test
63 				      * netif_xmit_frozen_or_stopped() before
64 				      * dequeueing next packet.
65 				      * Its true for MQ/MQPRIO slaves, or non
66 				      * multiqueue device.
67 				      */
68 #define TCQ_F_WARN_NONWC	(1 << 16)
69 #define TCQ_F_CPUSTATS		0x20 /* run using percpu statistics */
70 #define TCQ_F_NOPARENT		0x40 /* root of its hierarchy :
71 				      * qdisc_tree_decrease_qlen() should stop.
72 				      */
73 #define TCQ_F_INVISIBLE		0x80 /* invisible by default in dump */
74 #define TCQ_F_NOLOCK		0x100 /* qdisc does not require locking */
75 #define TCQ_F_OFFLOADED		0x200 /* qdisc is offloaded to HW */
76 	u32			limit;
77 	const struct Qdisc_ops	*ops;
78 	struct qdisc_size_table	__rcu *stab;
79 	struct hlist_node       hash;
80 	u32			handle;
81 	u32			parent;
82 
83 	struct netdev_queue	*dev_queue;
84 
85 	struct net_rate_estimator __rcu *rate_est;
86 	struct gnet_stats_basic_cpu __percpu *cpu_bstats;
87 	struct gnet_stats_queue	__percpu *cpu_qstats;
88 
89 	/*
90 	 * For performance sake on SMP, we put highly modified fields at the end
91 	 */
92 	struct sk_buff_head	gso_skb ____cacheline_aligned_in_smp;
93 	struct qdisc_skb_head	q;
94 	struct gnet_stats_basic_packed bstats;
95 	seqcount_t		running;
96 	struct gnet_stats_queue	qstats;
97 	unsigned long		state;
98 	struct Qdisc            *next_sched;
99 	struct sk_buff_head	skb_bad_txq;
100 	int			padded;
101 	refcount_t		refcnt;
102 
103 	spinlock_t		busylock ____cacheline_aligned_in_smp;
104 };
105 
106 static inline void qdisc_refcount_inc(struct Qdisc *qdisc)
107 {
108 	if (qdisc->flags & TCQ_F_BUILTIN)
109 		return;
110 	refcount_inc(&qdisc->refcnt);
111 }
112 
113 static inline bool qdisc_is_running(const struct Qdisc *qdisc)
114 {
115 	return (raw_read_seqcount(&qdisc->running) & 1) ? true : false;
116 }
117 
118 static inline bool qdisc_run_begin(struct Qdisc *qdisc)
119 {
120 	if (qdisc_is_running(qdisc))
121 		return false;
122 	/* Variant of write_seqcount_begin() telling lockdep a trylock
123 	 * was attempted.
124 	 */
125 	raw_write_seqcount_begin(&qdisc->running);
126 	seqcount_acquire(&qdisc->running.dep_map, 0, 1, _RET_IP_);
127 	return true;
128 }
129 
130 static inline void qdisc_run_end(struct Qdisc *qdisc)
131 {
132 	write_seqcount_end(&qdisc->running);
133 }
134 
135 static inline bool qdisc_may_bulk(const struct Qdisc *qdisc)
136 {
137 	return qdisc->flags & TCQ_F_ONETXQUEUE;
138 }
139 
140 static inline int qdisc_avail_bulklimit(const struct netdev_queue *txq)
141 {
142 #ifdef CONFIG_BQL
143 	/* Non-BQL migrated drivers will return 0, too. */
144 	return dql_avail(&txq->dql);
145 #else
146 	return 0;
147 #endif
148 }
149 
150 struct Qdisc_class_ops {
151 	/* Child qdisc manipulation */
152 	struct netdev_queue *	(*select_queue)(struct Qdisc *, struct tcmsg *);
153 	int			(*graft)(struct Qdisc *, unsigned long cl,
154 					struct Qdisc *, struct Qdisc **,
155 					struct netlink_ext_ack *extack);
156 	struct Qdisc *		(*leaf)(struct Qdisc *, unsigned long cl);
157 	void			(*qlen_notify)(struct Qdisc *, unsigned long);
158 
159 	/* Class manipulation routines */
160 	unsigned long		(*find)(struct Qdisc *, u32 classid);
161 	int			(*change)(struct Qdisc *, u32, u32,
162 					struct nlattr **, unsigned long *,
163 					struct netlink_ext_ack *);
164 	int			(*delete)(struct Qdisc *, unsigned long);
165 	void			(*walk)(struct Qdisc *, struct qdisc_walker * arg);
166 
167 	/* Filter manipulation */
168 	struct tcf_block *	(*tcf_block)(struct Qdisc *sch,
169 					     unsigned long arg,
170 					     struct netlink_ext_ack *extack);
171 	unsigned long		(*bind_tcf)(struct Qdisc *, unsigned long,
172 					u32 classid);
173 	void			(*unbind_tcf)(struct Qdisc *, unsigned long);
174 
175 	/* rtnetlink specific */
176 	int			(*dump)(struct Qdisc *, unsigned long,
177 					struct sk_buff *skb, struct tcmsg*);
178 	int			(*dump_stats)(struct Qdisc *, unsigned long,
179 					struct gnet_dump *);
180 };
181 
182 struct Qdisc_ops {
183 	struct Qdisc_ops	*next;
184 	const struct Qdisc_class_ops	*cl_ops;
185 	char			id[IFNAMSIZ];
186 	int			priv_size;
187 	unsigned int		static_flags;
188 
189 	int 			(*enqueue)(struct sk_buff *skb,
190 					   struct Qdisc *sch,
191 					   struct sk_buff **to_free);
192 	struct sk_buff *	(*dequeue)(struct Qdisc *);
193 	struct sk_buff *	(*peek)(struct Qdisc *);
194 
195 	int			(*init)(struct Qdisc *sch, struct nlattr *arg,
196 					struct netlink_ext_ack *extack);
197 	void			(*reset)(struct Qdisc *);
198 	void			(*destroy)(struct Qdisc *);
199 	int			(*change)(struct Qdisc *sch,
200 					  struct nlattr *arg,
201 					  struct netlink_ext_ack *extack);
202 	void			(*attach)(struct Qdisc *sch);
203 	int			(*change_tx_queue_len)(struct Qdisc *, unsigned int);
204 
205 	int			(*dump)(struct Qdisc *, struct sk_buff *);
206 	int			(*dump_stats)(struct Qdisc *, struct gnet_dump *);
207 
208 	void			(*ingress_block_set)(struct Qdisc *sch,
209 						     u32 block_index);
210 	void			(*egress_block_set)(struct Qdisc *sch,
211 						    u32 block_index);
212 	u32			(*ingress_block_get)(struct Qdisc *sch);
213 	u32			(*egress_block_get)(struct Qdisc *sch);
214 
215 	struct module		*owner;
216 };
217 
218 
219 struct tcf_result {
220 	union {
221 		struct {
222 			unsigned long	class;
223 			u32		classid;
224 		};
225 		const struct tcf_proto *goto_tp;
226 	};
227 };
228 
229 struct tcf_proto_ops {
230 	struct list_head	head;
231 	char			kind[IFNAMSIZ];
232 
233 	int			(*classify)(struct sk_buff *,
234 					    const struct tcf_proto *,
235 					    struct tcf_result *);
236 	int			(*init)(struct tcf_proto*);
237 	void			(*destroy)(struct tcf_proto *tp,
238 					   struct netlink_ext_ack *extack);
239 
240 	void*			(*get)(struct tcf_proto*, u32 handle);
241 	int			(*change)(struct net *net, struct sk_buff *,
242 					struct tcf_proto*, unsigned long,
243 					u32 handle, struct nlattr **,
244 					void **, bool,
245 					struct netlink_ext_ack *);
246 	int			(*delete)(struct tcf_proto *tp, void *arg,
247 					  bool *last,
248 					  struct netlink_ext_ack *);
249 	void			(*walk)(struct tcf_proto*, struct tcf_walker *arg);
250 	void			(*bind_class)(void *, u32, unsigned long);
251 
252 	/* rtnetlink specific */
253 	int			(*dump)(struct net*, struct tcf_proto*, void *,
254 					struct sk_buff *skb, struct tcmsg*);
255 
256 	struct module		*owner;
257 };
258 
259 struct tcf_proto {
260 	/* Fast access part */
261 	struct tcf_proto __rcu	*next;
262 	void __rcu		*root;
263 	int			(*classify)(struct sk_buff *,
264 					    const struct tcf_proto *,
265 					    struct tcf_result *);
266 	__be16			protocol;
267 
268 	/* All the rest */
269 	u32			prio;
270 	void			*data;
271 	const struct tcf_proto_ops	*ops;
272 	struct tcf_chain	*chain;
273 	struct rcu_head		rcu;
274 };
275 
276 struct qdisc_skb_cb {
277 	unsigned int		pkt_len;
278 	u16			slave_dev_queue_mapping;
279 	u16			tc_classid;
280 #define QDISC_CB_PRIV_LEN 20
281 	unsigned char		data[QDISC_CB_PRIV_LEN];
282 };
283 
284 typedef void tcf_chain_head_change_t(struct tcf_proto *tp_head, void *priv);
285 
286 struct tcf_chain {
287 	struct tcf_proto __rcu *filter_chain;
288 	struct list_head filter_chain_list;
289 	struct list_head list;
290 	struct tcf_block *block;
291 	u32 index; /* chain index */
292 	unsigned int refcnt;
293 };
294 
295 struct tcf_block {
296 	struct list_head chain_list;
297 	u32 index; /* block index for shared blocks */
298 	unsigned int refcnt;
299 	struct net *net;
300 	struct Qdisc *q;
301 	struct list_head cb_list;
302 	struct list_head owner_list;
303 	bool keep_dst;
304 	unsigned int offloadcnt; /* Number of oddloaded filters */
305 	unsigned int nooffloaddevcnt; /* Number of devs unable to do offload */
306 };
307 
308 static inline void tcf_block_offload_inc(struct tcf_block *block, u32 *flags)
309 {
310 	if (*flags & TCA_CLS_FLAGS_IN_HW)
311 		return;
312 	*flags |= TCA_CLS_FLAGS_IN_HW;
313 	block->offloadcnt++;
314 }
315 
316 static inline void tcf_block_offload_dec(struct tcf_block *block, u32 *flags)
317 {
318 	if (!(*flags & TCA_CLS_FLAGS_IN_HW))
319 		return;
320 	*flags &= ~TCA_CLS_FLAGS_IN_HW;
321 	block->offloadcnt--;
322 }
323 
324 static inline void qdisc_cb_private_validate(const struct sk_buff *skb, int sz)
325 {
326 	struct qdisc_skb_cb *qcb;
327 
328 	BUILD_BUG_ON(sizeof(skb->cb) < offsetof(struct qdisc_skb_cb, data) + sz);
329 	BUILD_BUG_ON(sizeof(qcb->data) < sz);
330 }
331 
332 static inline int qdisc_qlen_cpu(const struct Qdisc *q)
333 {
334 	return this_cpu_ptr(q->cpu_qstats)->qlen;
335 }
336 
337 static inline int qdisc_qlen(const struct Qdisc *q)
338 {
339 	return q->q.qlen;
340 }
341 
342 static inline int qdisc_qlen_sum(const struct Qdisc *q)
343 {
344 	__u32 qlen = 0;
345 	int i;
346 
347 	if (q->flags & TCQ_F_NOLOCK) {
348 		for_each_possible_cpu(i)
349 			qlen += per_cpu_ptr(q->cpu_qstats, i)->qlen;
350 	} else {
351 		qlen = q->q.qlen;
352 	}
353 
354 	return qlen;
355 }
356 
357 static inline struct qdisc_skb_cb *qdisc_skb_cb(const struct sk_buff *skb)
358 {
359 	return (struct qdisc_skb_cb *)skb->cb;
360 }
361 
362 static inline spinlock_t *qdisc_lock(struct Qdisc *qdisc)
363 {
364 	return &qdisc->q.lock;
365 }
366 
367 static inline struct Qdisc *qdisc_root(const struct Qdisc *qdisc)
368 {
369 	struct Qdisc *q = rcu_dereference_rtnl(qdisc->dev_queue->qdisc);
370 
371 	return q;
372 }
373 
374 static inline struct Qdisc *qdisc_root_sleeping(const struct Qdisc *qdisc)
375 {
376 	return qdisc->dev_queue->qdisc_sleeping;
377 }
378 
379 /* The qdisc root lock is a mechanism by which to top level
380  * of a qdisc tree can be locked from any qdisc node in the
381  * forest.  This allows changing the configuration of some
382  * aspect of the qdisc tree while blocking out asynchronous
383  * qdisc access in the packet processing paths.
384  *
385  * It is only legal to do this when the root will not change
386  * on us.  Otherwise we'll potentially lock the wrong qdisc
387  * root.  This is enforced by holding the RTNL semaphore, which
388  * all users of this lock accessor must do.
389  */
390 static inline spinlock_t *qdisc_root_lock(const struct Qdisc *qdisc)
391 {
392 	struct Qdisc *root = qdisc_root(qdisc);
393 
394 	ASSERT_RTNL();
395 	return qdisc_lock(root);
396 }
397 
398 static inline spinlock_t *qdisc_root_sleeping_lock(const struct Qdisc *qdisc)
399 {
400 	struct Qdisc *root = qdisc_root_sleeping(qdisc);
401 
402 	ASSERT_RTNL();
403 	return qdisc_lock(root);
404 }
405 
406 static inline seqcount_t *qdisc_root_sleeping_running(const struct Qdisc *qdisc)
407 {
408 	struct Qdisc *root = qdisc_root_sleeping(qdisc);
409 
410 	ASSERT_RTNL();
411 	return &root->running;
412 }
413 
414 static inline struct net_device *qdisc_dev(const struct Qdisc *qdisc)
415 {
416 	return qdisc->dev_queue->dev;
417 }
418 
419 static inline void sch_tree_lock(const struct Qdisc *q)
420 {
421 	spin_lock_bh(qdisc_root_sleeping_lock(q));
422 }
423 
424 static inline void sch_tree_unlock(const struct Qdisc *q)
425 {
426 	spin_unlock_bh(qdisc_root_sleeping_lock(q));
427 }
428 
429 extern struct Qdisc noop_qdisc;
430 extern struct Qdisc_ops noop_qdisc_ops;
431 extern struct Qdisc_ops pfifo_fast_ops;
432 extern struct Qdisc_ops mq_qdisc_ops;
433 extern struct Qdisc_ops noqueue_qdisc_ops;
434 extern const struct Qdisc_ops *default_qdisc_ops;
435 static inline const struct Qdisc_ops *
436 get_default_qdisc_ops(const struct net_device *dev, int ntx)
437 {
438 	return ntx < dev->real_num_tx_queues ?
439 			default_qdisc_ops : &pfifo_fast_ops;
440 }
441 
442 struct Qdisc_class_common {
443 	u32			classid;
444 	struct hlist_node	hnode;
445 };
446 
447 struct Qdisc_class_hash {
448 	struct hlist_head	*hash;
449 	unsigned int		hashsize;
450 	unsigned int		hashmask;
451 	unsigned int		hashelems;
452 };
453 
454 static inline unsigned int qdisc_class_hash(u32 id, u32 mask)
455 {
456 	id ^= id >> 8;
457 	id ^= id >> 4;
458 	return id & mask;
459 }
460 
461 static inline struct Qdisc_class_common *
462 qdisc_class_find(const struct Qdisc_class_hash *hash, u32 id)
463 {
464 	struct Qdisc_class_common *cl;
465 	unsigned int h;
466 
467 	if (!id)
468 		return NULL;
469 
470 	h = qdisc_class_hash(id, hash->hashmask);
471 	hlist_for_each_entry(cl, &hash->hash[h], hnode) {
472 		if (cl->classid == id)
473 			return cl;
474 	}
475 	return NULL;
476 }
477 
478 static inline int tc_classid_to_hwtc(struct net_device *dev, u32 classid)
479 {
480 	u32 hwtc = TC_H_MIN(classid) - TC_H_MIN_PRIORITY;
481 
482 	return (hwtc < netdev_get_num_tc(dev)) ? hwtc : -EINVAL;
483 }
484 
485 int qdisc_class_hash_init(struct Qdisc_class_hash *);
486 void qdisc_class_hash_insert(struct Qdisc_class_hash *,
487 			     struct Qdisc_class_common *);
488 void qdisc_class_hash_remove(struct Qdisc_class_hash *,
489 			     struct Qdisc_class_common *);
490 void qdisc_class_hash_grow(struct Qdisc *, struct Qdisc_class_hash *);
491 void qdisc_class_hash_destroy(struct Qdisc_class_hash *);
492 
493 int dev_qdisc_change_tx_queue_len(struct net_device *dev);
494 void dev_init_scheduler(struct net_device *dev);
495 void dev_shutdown(struct net_device *dev);
496 void dev_activate(struct net_device *dev);
497 void dev_deactivate(struct net_device *dev);
498 void dev_deactivate_many(struct list_head *head);
499 struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
500 			      struct Qdisc *qdisc);
501 void qdisc_reset(struct Qdisc *qdisc);
502 void qdisc_destroy(struct Qdisc *qdisc);
503 void qdisc_tree_reduce_backlog(struct Qdisc *qdisc, unsigned int n,
504 			       unsigned int len);
505 struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
506 			  const struct Qdisc_ops *ops,
507 			  struct netlink_ext_ack *extack);
508 void qdisc_free(struct Qdisc *qdisc);
509 struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue,
510 				const struct Qdisc_ops *ops, u32 parentid,
511 				struct netlink_ext_ack *extack);
512 void __qdisc_calculate_pkt_len(struct sk_buff *skb,
513 			       const struct qdisc_size_table *stab);
514 int skb_do_redirect(struct sk_buff *);
515 
516 static inline void skb_reset_tc(struct sk_buff *skb)
517 {
518 #ifdef CONFIG_NET_CLS_ACT
519 	skb->tc_redirected = 0;
520 #endif
521 }
522 
523 static inline bool skb_at_tc_ingress(const struct sk_buff *skb)
524 {
525 #ifdef CONFIG_NET_CLS_ACT
526 	return skb->tc_at_ingress;
527 #else
528 	return false;
529 #endif
530 }
531 
532 static inline bool skb_skip_tc_classify(struct sk_buff *skb)
533 {
534 #ifdef CONFIG_NET_CLS_ACT
535 	if (skb->tc_skip_classify) {
536 		skb->tc_skip_classify = 0;
537 		return true;
538 	}
539 #endif
540 	return false;
541 }
542 
543 /* Reset all TX qdiscs greater then index of a device.  */
544 static inline void qdisc_reset_all_tx_gt(struct net_device *dev, unsigned int i)
545 {
546 	struct Qdisc *qdisc;
547 
548 	for (; i < dev->num_tx_queues; i++) {
549 		qdisc = rtnl_dereference(netdev_get_tx_queue(dev, i)->qdisc);
550 		if (qdisc) {
551 			spin_lock_bh(qdisc_lock(qdisc));
552 			qdisc_reset(qdisc);
553 			spin_unlock_bh(qdisc_lock(qdisc));
554 		}
555 	}
556 }
557 
558 static inline void qdisc_reset_all_tx(struct net_device *dev)
559 {
560 	qdisc_reset_all_tx_gt(dev, 0);
561 }
562 
563 /* Are all TX queues of the device empty?  */
564 static inline bool qdisc_all_tx_empty(const struct net_device *dev)
565 {
566 	unsigned int i;
567 
568 	rcu_read_lock();
569 	for (i = 0; i < dev->num_tx_queues; i++) {
570 		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
571 		const struct Qdisc *q = rcu_dereference(txq->qdisc);
572 
573 		if (q->q.qlen) {
574 			rcu_read_unlock();
575 			return false;
576 		}
577 	}
578 	rcu_read_unlock();
579 	return true;
580 }
581 
582 /* Are any of the TX qdiscs changing?  */
583 static inline bool qdisc_tx_changing(const struct net_device *dev)
584 {
585 	unsigned int i;
586 
587 	for (i = 0; i < dev->num_tx_queues; i++) {
588 		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
589 		if (rcu_access_pointer(txq->qdisc) != txq->qdisc_sleeping)
590 			return true;
591 	}
592 	return false;
593 }
594 
595 /* Is the device using the noop qdisc on all queues?  */
596 static inline bool qdisc_tx_is_noop(const struct net_device *dev)
597 {
598 	unsigned int i;
599 
600 	for (i = 0; i < dev->num_tx_queues; i++) {
601 		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
602 		if (rcu_access_pointer(txq->qdisc) != &noop_qdisc)
603 			return false;
604 	}
605 	return true;
606 }
607 
608 static inline unsigned int qdisc_pkt_len(const struct sk_buff *skb)
609 {
610 	return qdisc_skb_cb(skb)->pkt_len;
611 }
612 
613 /* additional qdisc xmit flags (NET_XMIT_MASK in linux/netdevice.h) */
614 enum net_xmit_qdisc_t {
615 	__NET_XMIT_STOLEN = 0x00010000,
616 	__NET_XMIT_BYPASS = 0x00020000,
617 };
618 
619 #ifdef CONFIG_NET_CLS_ACT
620 #define net_xmit_drop_count(e)	((e) & __NET_XMIT_STOLEN ? 0 : 1)
621 #else
622 #define net_xmit_drop_count(e)	(1)
623 #endif
624 
625 static inline void qdisc_calculate_pkt_len(struct sk_buff *skb,
626 					   const struct Qdisc *sch)
627 {
628 #ifdef CONFIG_NET_SCHED
629 	struct qdisc_size_table *stab = rcu_dereference_bh(sch->stab);
630 
631 	if (stab)
632 		__qdisc_calculate_pkt_len(skb, stab);
633 #endif
634 }
635 
636 static inline int qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
637 				struct sk_buff **to_free)
638 {
639 	qdisc_calculate_pkt_len(skb, sch);
640 	return sch->enqueue(skb, sch, to_free);
641 }
642 
643 static inline bool qdisc_is_percpu_stats(const struct Qdisc *q)
644 {
645 	return q->flags & TCQ_F_CPUSTATS;
646 }
647 
648 static inline void _bstats_update(struct gnet_stats_basic_packed *bstats,
649 				  __u64 bytes, __u32 packets)
650 {
651 	bstats->bytes += bytes;
652 	bstats->packets += packets;
653 }
654 
655 static inline void bstats_update(struct gnet_stats_basic_packed *bstats,
656 				 const struct sk_buff *skb)
657 {
658 	_bstats_update(bstats,
659 		       qdisc_pkt_len(skb),
660 		       skb_is_gso(skb) ? skb_shinfo(skb)->gso_segs : 1);
661 }
662 
663 static inline void _bstats_cpu_update(struct gnet_stats_basic_cpu *bstats,
664 				      __u64 bytes, __u32 packets)
665 {
666 	u64_stats_update_begin(&bstats->syncp);
667 	_bstats_update(&bstats->bstats, bytes, packets);
668 	u64_stats_update_end(&bstats->syncp);
669 }
670 
671 static inline void bstats_cpu_update(struct gnet_stats_basic_cpu *bstats,
672 				     const struct sk_buff *skb)
673 {
674 	u64_stats_update_begin(&bstats->syncp);
675 	bstats_update(&bstats->bstats, skb);
676 	u64_stats_update_end(&bstats->syncp);
677 }
678 
679 static inline void qdisc_bstats_cpu_update(struct Qdisc *sch,
680 					   const struct sk_buff *skb)
681 {
682 	bstats_cpu_update(this_cpu_ptr(sch->cpu_bstats), skb);
683 }
684 
685 static inline void qdisc_bstats_update(struct Qdisc *sch,
686 				       const struct sk_buff *skb)
687 {
688 	bstats_update(&sch->bstats, skb);
689 }
690 
691 static inline void qdisc_qstats_backlog_dec(struct Qdisc *sch,
692 					    const struct sk_buff *skb)
693 {
694 	sch->qstats.backlog -= qdisc_pkt_len(skb);
695 }
696 
697 static inline void qdisc_qstats_cpu_backlog_dec(struct Qdisc *sch,
698 						const struct sk_buff *skb)
699 {
700 	this_cpu_sub(sch->cpu_qstats->backlog, qdisc_pkt_len(skb));
701 }
702 
703 static inline void qdisc_qstats_backlog_inc(struct Qdisc *sch,
704 					    const struct sk_buff *skb)
705 {
706 	sch->qstats.backlog += qdisc_pkt_len(skb);
707 }
708 
709 static inline void qdisc_qstats_cpu_backlog_inc(struct Qdisc *sch,
710 						const struct sk_buff *skb)
711 {
712 	this_cpu_add(sch->cpu_qstats->backlog, qdisc_pkt_len(skb));
713 }
714 
715 static inline void qdisc_qstats_cpu_qlen_inc(struct Qdisc *sch)
716 {
717 	this_cpu_inc(sch->cpu_qstats->qlen);
718 }
719 
720 static inline void qdisc_qstats_cpu_qlen_dec(struct Qdisc *sch)
721 {
722 	this_cpu_dec(sch->cpu_qstats->qlen);
723 }
724 
725 static inline void qdisc_qstats_cpu_requeues_inc(struct Qdisc *sch)
726 {
727 	this_cpu_inc(sch->cpu_qstats->requeues);
728 }
729 
730 static inline void __qdisc_qstats_drop(struct Qdisc *sch, int count)
731 {
732 	sch->qstats.drops += count;
733 }
734 
735 static inline void qstats_drop_inc(struct gnet_stats_queue *qstats)
736 {
737 	qstats->drops++;
738 }
739 
740 static inline void qstats_overlimit_inc(struct gnet_stats_queue *qstats)
741 {
742 	qstats->overlimits++;
743 }
744 
745 static inline void qdisc_qstats_drop(struct Qdisc *sch)
746 {
747 	qstats_drop_inc(&sch->qstats);
748 }
749 
750 static inline void qdisc_qstats_cpu_drop(struct Qdisc *sch)
751 {
752 	this_cpu_inc(sch->cpu_qstats->drops);
753 }
754 
755 static inline void qdisc_qstats_overlimit(struct Qdisc *sch)
756 {
757 	sch->qstats.overlimits++;
758 }
759 
760 static inline void qdisc_skb_head_init(struct qdisc_skb_head *qh)
761 {
762 	qh->head = NULL;
763 	qh->tail = NULL;
764 	qh->qlen = 0;
765 }
766 
767 static inline int __qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch,
768 				       struct qdisc_skb_head *qh)
769 {
770 	struct sk_buff *last = qh->tail;
771 
772 	if (last) {
773 		skb->next = NULL;
774 		last->next = skb;
775 		qh->tail = skb;
776 	} else {
777 		qh->tail = skb;
778 		qh->head = skb;
779 	}
780 	qh->qlen++;
781 	qdisc_qstats_backlog_inc(sch, skb);
782 
783 	return NET_XMIT_SUCCESS;
784 }
785 
786 static inline int qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch)
787 {
788 	return __qdisc_enqueue_tail(skb, sch, &sch->q);
789 }
790 
791 static inline struct sk_buff *__qdisc_dequeue_head(struct qdisc_skb_head *qh)
792 {
793 	struct sk_buff *skb = qh->head;
794 
795 	if (likely(skb != NULL)) {
796 		qh->head = skb->next;
797 		qh->qlen--;
798 		if (qh->head == NULL)
799 			qh->tail = NULL;
800 		skb->next = NULL;
801 	}
802 
803 	return skb;
804 }
805 
806 static inline struct sk_buff *qdisc_dequeue_head(struct Qdisc *sch)
807 {
808 	struct sk_buff *skb = __qdisc_dequeue_head(&sch->q);
809 
810 	if (likely(skb != NULL)) {
811 		qdisc_qstats_backlog_dec(sch, skb);
812 		qdisc_bstats_update(sch, skb);
813 	}
814 
815 	return skb;
816 }
817 
818 /* Instead of calling kfree_skb() while root qdisc lock is held,
819  * queue the skb for future freeing at end of __dev_xmit_skb()
820  */
821 static inline void __qdisc_drop(struct sk_buff *skb, struct sk_buff **to_free)
822 {
823 	skb->next = *to_free;
824 	*to_free = skb;
825 }
826 
827 static inline unsigned int __qdisc_queue_drop_head(struct Qdisc *sch,
828 						   struct qdisc_skb_head *qh,
829 						   struct sk_buff **to_free)
830 {
831 	struct sk_buff *skb = __qdisc_dequeue_head(qh);
832 
833 	if (likely(skb != NULL)) {
834 		unsigned int len = qdisc_pkt_len(skb);
835 
836 		qdisc_qstats_backlog_dec(sch, skb);
837 		__qdisc_drop(skb, to_free);
838 		return len;
839 	}
840 
841 	return 0;
842 }
843 
844 static inline unsigned int qdisc_queue_drop_head(struct Qdisc *sch,
845 						 struct sk_buff **to_free)
846 {
847 	return __qdisc_queue_drop_head(sch, &sch->q, to_free);
848 }
849 
850 static inline struct sk_buff *qdisc_peek_head(struct Qdisc *sch)
851 {
852 	const struct qdisc_skb_head *qh = &sch->q;
853 
854 	return qh->head;
855 }
856 
857 /* generic pseudo peek method for non-work-conserving qdisc */
858 static inline struct sk_buff *qdisc_peek_dequeued(struct Qdisc *sch)
859 {
860 	struct sk_buff *skb = skb_peek(&sch->gso_skb);
861 
862 	/* we can reuse ->gso_skb because peek isn't called for root qdiscs */
863 	if (!skb) {
864 		skb = sch->dequeue(sch);
865 
866 		if (skb) {
867 			__skb_queue_head(&sch->gso_skb, skb);
868 			/* it's still part of the queue */
869 			qdisc_qstats_backlog_inc(sch, skb);
870 			sch->q.qlen++;
871 		}
872 	}
873 
874 	return skb;
875 }
876 
877 /* use instead of qdisc->dequeue() for all qdiscs queried with ->peek() */
878 static inline struct sk_buff *qdisc_dequeue_peeked(struct Qdisc *sch)
879 {
880 	struct sk_buff *skb = skb_peek(&sch->gso_skb);
881 
882 	if (skb) {
883 		skb = __skb_dequeue(&sch->gso_skb);
884 		qdisc_qstats_backlog_dec(sch, skb);
885 		sch->q.qlen--;
886 	} else {
887 		skb = sch->dequeue(sch);
888 	}
889 
890 	return skb;
891 }
892 
893 static inline void __qdisc_reset_queue(struct qdisc_skb_head *qh)
894 {
895 	/*
896 	 * We do not know the backlog in bytes of this list, it
897 	 * is up to the caller to correct it
898 	 */
899 	ASSERT_RTNL();
900 	if (qh->qlen) {
901 		rtnl_kfree_skbs(qh->head, qh->tail);
902 
903 		qh->head = NULL;
904 		qh->tail = NULL;
905 		qh->qlen = 0;
906 	}
907 }
908 
909 static inline void qdisc_reset_queue(struct Qdisc *sch)
910 {
911 	__qdisc_reset_queue(&sch->q);
912 	sch->qstats.backlog = 0;
913 }
914 
915 static inline struct Qdisc *qdisc_replace(struct Qdisc *sch, struct Qdisc *new,
916 					  struct Qdisc **pold)
917 {
918 	struct Qdisc *old;
919 
920 	sch_tree_lock(sch);
921 	old = *pold;
922 	*pold = new;
923 	if (old != NULL) {
924 		unsigned int qlen = old->q.qlen;
925 		unsigned int backlog = old->qstats.backlog;
926 
927 		qdisc_reset(old);
928 		qdisc_tree_reduce_backlog(old, qlen, backlog);
929 	}
930 	sch_tree_unlock(sch);
931 
932 	return old;
933 }
934 
935 static inline void rtnl_qdisc_drop(struct sk_buff *skb, struct Qdisc *sch)
936 {
937 	rtnl_kfree_skbs(skb, skb);
938 	qdisc_qstats_drop(sch);
939 }
940 
941 static inline int qdisc_drop_cpu(struct sk_buff *skb, struct Qdisc *sch,
942 				 struct sk_buff **to_free)
943 {
944 	__qdisc_drop(skb, to_free);
945 	qdisc_qstats_cpu_drop(sch);
946 
947 	return NET_XMIT_DROP;
948 }
949 
950 static inline int qdisc_drop(struct sk_buff *skb, struct Qdisc *sch,
951 			     struct sk_buff **to_free)
952 {
953 	__qdisc_drop(skb, to_free);
954 	qdisc_qstats_drop(sch);
955 
956 	return NET_XMIT_DROP;
957 }
958 
959 /* Length to Time (L2T) lookup in a qdisc_rate_table, to determine how
960    long it will take to send a packet given its size.
961  */
962 static inline u32 qdisc_l2t(struct qdisc_rate_table* rtab, unsigned int pktlen)
963 {
964 	int slot = pktlen + rtab->rate.cell_align + rtab->rate.overhead;
965 	if (slot < 0)
966 		slot = 0;
967 	slot >>= rtab->rate.cell_log;
968 	if (slot > 255)
969 		return rtab->data[255]*(slot >> 8) + rtab->data[slot & 0xFF];
970 	return rtab->data[slot];
971 }
972 
973 struct psched_ratecfg {
974 	u64	rate_bytes_ps; /* bytes per second */
975 	u32	mult;
976 	u16	overhead;
977 	u8	linklayer;
978 	u8	shift;
979 };
980 
981 static inline u64 psched_l2t_ns(const struct psched_ratecfg *r,
982 				unsigned int len)
983 {
984 	len += r->overhead;
985 
986 	if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
987 		return ((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift;
988 
989 	return ((u64)len * r->mult) >> r->shift;
990 }
991 
992 void psched_ratecfg_precompute(struct psched_ratecfg *r,
993 			       const struct tc_ratespec *conf,
994 			       u64 rate64);
995 
996 static inline void psched_ratecfg_getrate(struct tc_ratespec *res,
997 					  const struct psched_ratecfg *r)
998 {
999 	memset(res, 0, sizeof(*res));
1000 
1001 	/* legacy struct tc_ratespec has a 32bit @rate field
1002 	 * Qdisc using 64bit rate should add new attributes
1003 	 * in order to maintain compatibility.
1004 	 */
1005 	res->rate = min_t(u64, r->rate_bytes_ps, ~0U);
1006 
1007 	res->overhead = r->overhead;
1008 	res->linklayer = (r->linklayer & TC_LINKLAYER_MASK);
1009 }
1010 
1011 /* Mini Qdisc serves for specific needs of ingress/clsact Qdisc.
1012  * The fast path only needs to access filter list and to update stats
1013  */
1014 struct mini_Qdisc {
1015 	struct tcf_proto *filter_list;
1016 	struct gnet_stats_basic_cpu __percpu *cpu_bstats;
1017 	struct gnet_stats_queue	__percpu *cpu_qstats;
1018 	struct rcu_head rcu;
1019 };
1020 
1021 static inline void mini_qdisc_bstats_cpu_update(struct mini_Qdisc *miniq,
1022 						const struct sk_buff *skb)
1023 {
1024 	bstats_cpu_update(this_cpu_ptr(miniq->cpu_bstats), skb);
1025 }
1026 
1027 static inline void mini_qdisc_qstats_cpu_drop(struct mini_Qdisc *miniq)
1028 {
1029 	this_cpu_inc(miniq->cpu_qstats->drops);
1030 }
1031 
1032 struct mini_Qdisc_pair {
1033 	struct mini_Qdisc miniq1;
1034 	struct mini_Qdisc miniq2;
1035 	struct mini_Qdisc __rcu **p_miniq;
1036 };
1037 
1038 void mini_qdisc_pair_swap(struct mini_Qdisc_pair *miniqp,
1039 			  struct tcf_proto *tp_head);
1040 void mini_qdisc_pair_init(struct mini_Qdisc_pair *miniqp, struct Qdisc *qdisc,
1041 			  struct mini_Qdisc __rcu **p_miniq);
1042 
1043 #endif
1044