1 #ifndef __NET_SCHED_GENERIC_H
2 #define __NET_SCHED_GENERIC_H
4 #include <linux/netdevice.h>
5 #include <linux/types.h>
6 #include <linux/rcupdate.h>
7 #include <linux/pkt_sched.h>
8 #include <linux/pkt_cls.h>
9 #include <net/gen_stats.h>
10 #include <net/rtnetlink.h>
17 struct qdisc_rate_table
{
18 struct tc_ratespec rate
;
20 struct qdisc_rate_table
*next
;
26 __QDISC_STATE_DEACTIVATED
,
27 __QDISC_STATE_THROTTLED
,
31 * following bits are only changed while qdisc lock is held
33 enum qdisc___state_t
{
34 __QDISC___STATE_RUNNING
= 1,
37 struct qdisc_size_table
{
39 struct list_head list
;
40 struct tc_sizespec szopts
;
46 int (*enqueue
)(struct sk_buff
*skb
, struct Qdisc
*dev
);
47 struct sk_buff
* (*dequeue
)(struct Qdisc
*dev
);
49 #define TCQ_F_BUILTIN 1
50 #define TCQ_F_INGRESS 2
51 #define TCQ_F_CAN_BYPASS 4
52 #define TCQ_F_MQROOT 8
53 #define TCQ_F_ONETXQUEUE 0x10 /* dequeue_skb() can assume all skbs are for
54 * q->dev_queue : It can test
55 * netif_xmit_frozen_or_stopped() before
56 * dequeueing next packet.
57 * Its true for MQ/MQPRIO slaves, or non
60 #define TCQ_F_WARN_NONWC (1 << 16)
62 const struct Qdisc_ops
*ops
;
63 struct qdisc_size_table __rcu
*stab
;
64 struct list_head list
;
68 struct gnet_stats_rate_est rate_est
;
69 int (*reshape_fail
)(struct sk_buff
*skb
,
74 /* This field is deprecated, but it is still used by CBQ
75 * and it will live until better solution will be invented.
77 struct Qdisc
*__parent
;
78 struct netdev_queue
*dev_queue
;
79 struct Qdisc
*next_sched
;
81 struct sk_buff
*gso_skb
;
83 * For performance sake on SMP, we put highly modified fields at the end
86 struct sk_buff_head q
;
87 struct gnet_stats_basic_packed bstats
;
89 struct gnet_stats_queue qstats
;
90 struct rcu_head rcu_head
;
95 static inline bool qdisc_is_running(const struct Qdisc
*qdisc
)
97 return (qdisc
->__state
& __QDISC___STATE_RUNNING
) ? true : false;
100 static inline bool qdisc_run_begin(struct Qdisc
*qdisc
)
102 if (qdisc_is_running(qdisc
))
104 qdisc
->__state
|= __QDISC___STATE_RUNNING
;
108 static inline void qdisc_run_end(struct Qdisc
*qdisc
)
110 qdisc
->__state
&= ~__QDISC___STATE_RUNNING
;
113 static inline bool qdisc_is_throttled(const struct Qdisc
*qdisc
)
115 return test_bit(__QDISC_STATE_THROTTLED
, &qdisc
->state
) ? true : false;
118 static inline void qdisc_throttled(struct Qdisc
*qdisc
)
120 set_bit(__QDISC_STATE_THROTTLED
, &qdisc
->state
);
123 static inline void qdisc_unthrottled(struct Qdisc
*qdisc
)
125 clear_bit(__QDISC_STATE_THROTTLED
, &qdisc
->state
);
128 struct Qdisc_class_ops
{
129 /* Child qdisc manipulation */
130 struct netdev_queue
* (*select_queue
)(struct Qdisc
*, struct tcmsg
*);
131 int (*graft
)(struct Qdisc
*, unsigned long cl
,
132 struct Qdisc
*, struct Qdisc
**);
133 struct Qdisc
* (*leaf
)(struct Qdisc
*, unsigned long cl
);
134 void (*qlen_notify
)(struct Qdisc
*, unsigned long);
136 /* Class manipulation routines */
137 unsigned long (*get
)(struct Qdisc
*, u32 classid
);
138 void (*put
)(struct Qdisc
*, unsigned long);
139 int (*change
)(struct Qdisc
*, u32
, u32
,
140 struct nlattr
**, unsigned long *);
141 int (*delete)(struct Qdisc
*, unsigned long);
142 void (*walk
)(struct Qdisc
*, struct qdisc_walker
* arg
);
144 /* Filter manipulation */
145 struct tcf_proto
** (*tcf_chain
)(struct Qdisc
*, unsigned long);
146 unsigned long (*bind_tcf
)(struct Qdisc
*, unsigned long,
148 void (*unbind_tcf
)(struct Qdisc
*, unsigned long);
150 /* rtnetlink specific */
151 int (*dump
)(struct Qdisc
*, unsigned long,
152 struct sk_buff
*skb
, struct tcmsg
*);
153 int (*dump_stats
)(struct Qdisc
*, unsigned long,
158 struct Qdisc_ops
*next
;
159 const struct Qdisc_class_ops
*cl_ops
;
163 int (*enqueue
)(struct sk_buff
*, struct Qdisc
*);
164 struct sk_buff
* (*dequeue
)(struct Qdisc
*);
165 struct sk_buff
* (*peek
)(struct Qdisc
*);
166 unsigned int (*drop
)(struct Qdisc
*);
168 int (*init
)(struct Qdisc
*, struct nlattr
*arg
);
169 void (*reset
)(struct Qdisc
*);
170 void (*destroy
)(struct Qdisc
*);
171 int (*change
)(struct Qdisc
*, struct nlattr
*arg
);
172 void (*attach
)(struct Qdisc
*);
174 int (*dump
)(struct Qdisc
*, struct sk_buff
*);
175 int (*dump_stats
)(struct Qdisc
*, struct gnet_dump
*);
177 struct module
*owner
;
186 struct tcf_proto_ops
{
187 struct tcf_proto_ops
*next
;
190 int (*classify
)(struct sk_buff
*,
191 const struct tcf_proto
*,
192 struct tcf_result
*);
193 int (*init
)(struct tcf_proto
*);
194 void (*destroy
)(struct tcf_proto
*);
196 unsigned long (*get
)(struct tcf_proto
*, u32 handle
);
197 void (*put
)(struct tcf_proto
*, unsigned long);
198 int (*change
)(struct net
*net
, struct sk_buff
*,
199 struct tcf_proto
*, unsigned long,
200 u32 handle
, struct nlattr
**,
202 int (*delete)(struct tcf_proto
*, unsigned long);
203 void (*walk
)(struct tcf_proto
*, struct tcf_walker
*arg
);
205 /* rtnetlink specific */
206 int (*dump
)(struct tcf_proto
*, unsigned long,
207 struct sk_buff
*skb
, struct tcmsg
*);
209 struct module
*owner
;
213 /* Fast access part */
214 struct tcf_proto
*next
;
216 int (*classify
)(struct sk_buff
*,
217 const struct tcf_proto
*,
218 struct tcf_result
*);
226 const struct tcf_proto_ops
*ops
;
229 struct qdisc_skb_cb
{
230 unsigned int pkt_len
;
231 u16 slave_dev_queue_mapping
;
233 unsigned char data
[20];
236 static inline void qdisc_cb_private_validate(const struct sk_buff
*skb
, int sz
)
238 struct qdisc_skb_cb
*qcb
;
240 BUILD_BUG_ON(sizeof(skb
->cb
) < offsetof(struct qdisc_skb_cb
, data
) + sz
);
241 BUILD_BUG_ON(sizeof(qcb
->data
) < sz
);
244 static inline int qdisc_qlen(const struct Qdisc
*q
)
249 static inline struct qdisc_skb_cb
*qdisc_skb_cb(const struct sk_buff
*skb
)
251 return (struct qdisc_skb_cb
*)skb
->cb
;
254 static inline spinlock_t
*qdisc_lock(struct Qdisc
*qdisc
)
256 return &qdisc
->q
.lock
;
259 static inline struct Qdisc
*qdisc_root(const struct Qdisc
*qdisc
)
261 return qdisc
->dev_queue
->qdisc
;
264 static inline struct Qdisc
*qdisc_root_sleeping(const struct Qdisc
*qdisc
)
266 return qdisc
->dev_queue
->qdisc_sleeping
;
269 /* The qdisc root lock is a mechanism by which to top level
270 * of a qdisc tree can be locked from any qdisc node in the
271 * forest. This allows changing the configuration of some
272 * aspect of the qdisc tree while blocking out asynchronous
273 * qdisc access in the packet processing paths.
275 * It is only legal to do this when the root will not change
276 * on us. Otherwise we'll potentially lock the wrong qdisc
277 * root. This is enforced by holding the RTNL semaphore, which
278 * all users of this lock accessor must do.
280 static inline spinlock_t
*qdisc_root_lock(const struct Qdisc
*qdisc
)
282 struct Qdisc
*root
= qdisc_root(qdisc
);
285 return qdisc_lock(root
);
288 static inline spinlock_t
*qdisc_root_sleeping_lock(const struct Qdisc
*qdisc
)
290 struct Qdisc
*root
= qdisc_root_sleeping(qdisc
);
293 return qdisc_lock(root
);
296 static inline struct net_device
*qdisc_dev(const struct Qdisc
*qdisc
)
298 return qdisc
->dev_queue
->dev
;
301 static inline void sch_tree_lock(const struct Qdisc
*q
)
303 spin_lock_bh(qdisc_root_sleeping_lock(q
));
306 static inline void sch_tree_unlock(const struct Qdisc
*q
)
308 spin_unlock_bh(qdisc_root_sleeping_lock(q
));
311 #define tcf_tree_lock(tp) sch_tree_lock((tp)->q)
312 #define tcf_tree_unlock(tp) sch_tree_unlock((tp)->q)
314 extern struct Qdisc noop_qdisc
;
315 extern struct Qdisc_ops noop_qdisc_ops
;
316 extern struct Qdisc_ops pfifo_fast_ops
;
317 extern struct Qdisc_ops mq_qdisc_ops
;
319 struct Qdisc_class_common
{
321 struct hlist_node hnode
;
324 struct Qdisc_class_hash
{
325 struct hlist_head
*hash
;
326 unsigned int hashsize
;
327 unsigned int hashmask
;
328 unsigned int hashelems
;
331 static inline unsigned int qdisc_class_hash(u32 id
, u32 mask
)
338 static inline struct Qdisc_class_common
*
339 qdisc_class_find(const struct Qdisc_class_hash
*hash
, u32 id
)
341 struct Qdisc_class_common
*cl
;
344 h
= qdisc_class_hash(id
, hash
->hashmask
);
345 hlist_for_each_entry(cl
, &hash
->hash
[h
], hnode
) {
346 if (cl
->classid
== id
)
352 extern int qdisc_class_hash_init(struct Qdisc_class_hash
*);
353 extern void qdisc_class_hash_insert(struct Qdisc_class_hash
*, struct Qdisc_class_common
*);
354 extern void qdisc_class_hash_remove(struct Qdisc_class_hash
*, struct Qdisc_class_common
*);
355 extern void qdisc_class_hash_grow(struct Qdisc
*, struct Qdisc_class_hash
*);
356 extern void qdisc_class_hash_destroy(struct Qdisc_class_hash
*);
358 extern void dev_init_scheduler(struct net_device
*dev
);
359 extern void dev_shutdown(struct net_device
*dev
);
360 extern void dev_activate(struct net_device
*dev
);
361 extern void dev_deactivate(struct net_device
*dev
);
362 extern void dev_deactivate_many(struct list_head
*head
);
363 extern struct Qdisc
*dev_graft_qdisc(struct netdev_queue
*dev_queue
,
364 struct Qdisc
*qdisc
);
365 extern void qdisc_reset(struct Qdisc
*qdisc
);
366 extern void qdisc_destroy(struct Qdisc
*qdisc
);
367 extern void qdisc_tree_decrease_qlen(struct Qdisc
*qdisc
, unsigned int n
);
368 extern struct Qdisc
*qdisc_alloc(struct netdev_queue
*dev_queue
,
369 struct Qdisc_ops
*ops
);
370 extern struct Qdisc
*qdisc_create_dflt(struct netdev_queue
*dev_queue
,
371 struct Qdisc_ops
*ops
, u32 parentid
);
372 extern void __qdisc_calculate_pkt_len(struct sk_buff
*skb
,
373 const struct qdisc_size_table
*stab
);
374 extern void tcf_destroy(struct tcf_proto
*tp
);
375 extern void tcf_destroy_chain(struct tcf_proto
**fl
);
377 /* Reset all TX qdiscs greater then index of a device. */
378 static inline void qdisc_reset_all_tx_gt(struct net_device
*dev
, unsigned int i
)
382 for (; i
< dev
->num_tx_queues
; i
++) {
383 qdisc
= netdev_get_tx_queue(dev
, i
)->qdisc
;
385 spin_lock_bh(qdisc_lock(qdisc
));
387 spin_unlock_bh(qdisc_lock(qdisc
));
392 static inline void qdisc_reset_all_tx(struct net_device
*dev
)
394 qdisc_reset_all_tx_gt(dev
, 0);
397 /* Are all TX queues of the device empty? */
398 static inline bool qdisc_all_tx_empty(const struct net_device
*dev
)
401 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
402 struct netdev_queue
*txq
= netdev_get_tx_queue(dev
, i
);
403 const struct Qdisc
*q
= txq
->qdisc
;
411 /* Are any of the TX qdiscs changing? */
412 static inline bool qdisc_tx_changing(const struct net_device
*dev
)
415 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
416 struct netdev_queue
*txq
= netdev_get_tx_queue(dev
, i
);
417 if (txq
->qdisc
!= txq
->qdisc_sleeping
)
423 /* Is the device using the noop qdisc on all queues? */
424 static inline bool qdisc_tx_is_noop(const struct net_device
*dev
)
427 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
428 struct netdev_queue
*txq
= netdev_get_tx_queue(dev
, i
);
429 if (txq
->qdisc
!= &noop_qdisc
)
435 static inline unsigned int qdisc_pkt_len(const struct sk_buff
*skb
)
437 return qdisc_skb_cb(skb
)->pkt_len
;
440 /* additional qdisc xmit flags (NET_XMIT_MASK in linux/netdevice.h) */
441 enum net_xmit_qdisc_t
{
442 __NET_XMIT_STOLEN
= 0x00010000,
443 __NET_XMIT_BYPASS
= 0x00020000,
446 #ifdef CONFIG_NET_CLS_ACT
447 #define net_xmit_drop_count(e) ((e) & __NET_XMIT_STOLEN ? 0 : 1)
449 #define net_xmit_drop_count(e) (1)
452 static inline void qdisc_calculate_pkt_len(struct sk_buff
*skb
,
453 const struct Qdisc
*sch
)
455 #ifdef CONFIG_NET_SCHED
456 struct qdisc_size_table
*stab
= rcu_dereference_bh(sch
->stab
);
459 __qdisc_calculate_pkt_len(skb
, stab
);
463 static inline int qdisc_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
465 qdisc_calculate_pkt_len(skb
, sch
);
466 return sch
->enqueue(skb
, sch
);
469 static inline int qdisc_enqueue_root(struct sk_buff
*skb
, struct Qdisc
*sch
)
471 qdisc_skb_cb(skb
)->pkt_len
= skb
->len
;
472 return qdisc_enqueue(skb
, sch
) & NET_XMIT_MASK
;
476 static inline void bstats_update(struct gnet_stats_basic_packed
*bstats
,
477 const struct sk_buff
*skb
)
479 bstats
->bytes
+= qdisc_pkt_len(skb
);
480 bstats
->packets
+= skb_is_gso(skb
) ? skb_shinfo(skb
)->gso_segs
: 1;
483 static inline void qdisc_bstats_update(struct Qdisc
*sch
,
484 const struct sk_buff
*skb
)
486 bstats_update(&sch
->bstats
, skb
);
489 static inline int __qdisc_enqueue_tail(struct sk_buff
*skb
, struct Qdisc
*sch
,
490 struct sk_buff_head
*list
)
492 __skb_queue_tail(list
, skb
);
493 sch
->qstats
.backlog
+= qdisc_pkt_len(skb
);
495 return NET_XMIT_SUCCESS
;
498 static inline int qdisc_enqueue_tail(struct sk_buff
*skb
, struct Qdisc
*sch
)
500 return __qdisc_enqueue_tail(skb
, sch
, &sch
->q
);
503 static inline struct sk_buff
*__qdisc_dequeue_head(struct Qdisc
*sch
,
504 struct sk_buff_head
*list
)
506 struct sk_buff
*skb
= __skb_dequeue(list
);
508 if (likely(skb
!= NULL
)) {
509 sch
->qstats
.backlog
-= qdisc_pkt_len(skb
);
510 qdisc_bstats_update(sch
, skb
);
516 static inline struct sk_buff
*qdisc_dequeue_head(struct Qdisc
*sch
)
518 return __qdisc_dequeue_head(sch
, &sch
->q
);
521 static inline unsigned int __qdisc_queue_drop_head(struct Qdisc
*sch
,
522 struct sk_buff_head
*list
)
524 struct sk_buff
*skb
= __skb_dequeue(list
);
526 if (likely(skb
!= NULL
)) {
527 unsigned int len
= qdisc_pkt_len(skb
);
528 sch
->qstats
.backlog
-= len
;
536 static inline unsigned int qdisc_queue_drop_head(struct Qdisc
*sch
)
538 return __qdisc_queue_drop_head(sch
, &sch
->q
);
541 static inline struct sk_buff
*__qdisc_dequeue_tail(struct Qdisc
*sch
,
542 struct sk_buff_head
*list
)
544 struct sk_buff
*skb
= __skb_dequeue_tail(list
);
546 if (likely(skb
!= NULL
))
547 sch
->qstats
.backlog
-= qdisc_pkt_len(skb
);
552 static inline struct sk_buff
*qdisc_dequeue_tail(struct Qdisc
*sch
)
554 return __qdisc_dequeue_tail(sch
, &sch
->q
);
557 static inline struct sk_buff
*qdisc_peek_head(struct Qdisc
*sch
)
559 return skb_peek(&sch
->q
);
562 /* generic pseudo peek method for non-work-conserving qdisc */
563 static inline struct sk_buff
*qdisc_peek_dequeued(struct Qdisc
*sch
)
565 /* we can reuse ->gso_skb because peek isn't called for root qdiscs */
567 sch
->gso_skb
= sch
->dequeue(sch
);
569 /* it's still part of the queue */
576 /* use instead of qdisc->dequeue() for all qdiscs queried with ->peek() */
577 static inline struct sk_buff
*qdisc_dequeue_peeked(struct Qdisc
*sch
)
579 struct sk_buff
*skb
= sch
->gso_skb
;
585 skb
= sch
->dequeue(sch
);
591 static inline void __qdisc_reset_queue(struct Qdisc
*sch
,
592 struct sk_buff_head
*list
)
595 * We do not know the backlog in bytes of this list, it
596 * is up to the caller to correct it
598 __skb_queue_purge(list
);
601 static inline void qdisc_reset_queue(struct Qdisc
*sch
)
603 __qdisc_reset_queue(sch
, &sch
->q
);
604 sch
->qstats
.backlog
= 0;
607 static inline unsigned int __qdisc_queue_drop(struct Qdisc
*sch
,
608 struct sk_buff_head
*list
)
610 struct sk_buff
*skb
= __qdisc_dequeue_tail(sch
, list
);
612 if (likely(skb
!= NULL
)) {
613 unsigned int len
= qdisc_pkt_len(skb
);
621 static inline unsigned int qdisc_queue_drop(struct Qdisc
*sch
)
623 return __qdisc_queue_drop(sch
, &sch
->q
);
626 static inline int qdisc_drop(struct sk_buff
*skb
, struct Qdisc
*sch
)
631 return NET_XMIT_DROP
;
634 static inline int qdisc_reshape_fail(struct sk_buff
*skb
, struct Qdisc
*sch
)
638 #ifdef CONFIG_NET_CLS_ACT
639 if (sch
->reshape_fail
== NULL
|| sch
->reshape_fail(skb
, sch
))
642 return NET_XMIT_SUCCESS
;
647 return NET_XMIT_DROP
;
650 /* Length to Time (L2T) lookup in a qdisc_rate_table, to determine how
651 long it will take to send a packet given its size.
653 static inline u32
qdisc_l2t(struct qdisc_rate_table
* rtab
, unsigned int pktlen
)
655 int slot
= pktlen
+ rtab
->rate
.cell_align
+ rtab
->rate
.overhead
;
658 slot
>>= rtab
->rate
.cell_log
;
660 return rtab
->data
[255]*(slot
>> 8) + rtab
->data
[slot
& 0xFF];
661 return rtab
->data
[slot
];
664 #ifdef CONFIG_NET_CLS_ACT
665 static inline struct sk_buff
*skb_act_clone(struct sk_buff
*skb
, gfp_t gfp_mask
,
670 n
= skb_clone(skb
, gfp_mask
);
673 n
->tc_verd
= SET_TC_VERD(n
->tc_verd
, 0);
674 n
->tc_verd
= CLR_TC_OK2MUNGE(n
->tc_verd
);
675 n
->tc_verd
= CLR_TC_MUNGED(n
->tc_verd
);
681 struct psched_ratecfg
{
689 static inline u64
psched_l2t_ns(const struct psched_ratecfg
*r
,
694 if (unlikely(r
->linklayer
== TC_LINKLAYER_ATM
))
695 return ((u64
)(DIV_ROUND_UP(len
,48)*53) * r
->mult
) >> r
->shift
;
697 return ((u64
)len
* r
->mult
) >> r
->shift
;
700 extern void psched_ratecfg_precompute(struct psched_ratecfg
*r
, const struct tc_ratespec
*conf
);
702 static inline void psched_ratecfg_getrate(struct tc_ratespec
*res
,
703 const struct psched_ratecfg
*r
)
705 memset(res
, 0, sizeof(*res
));
706 res
->rate
= r
->rate_bps
>> 3;
707 res
->overhead
= r
->overhead
;
708 res
->linklayer
= (r
->linklayer
& TC_LINKLAYER_MASK
);