include/net/sch_generic.h

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