include/net/sch_generic.h

   1 #ifndef __NET_SCHED_GENERIC_H
   2 #define __NET_SCHED_GENERIC_H
   3
   4 #include <linux/netdevice.h>
   5 #include <linux/types.h>
   6 #include <linux/rcupdate.h>
   7 #include <linux/module.h>
   8 #include <linux/pkt_sched.h>
   9 #include <linux/pkt_cls.h>
  10 #include <net/gen_stats.h>
  11 #include <net/rtnetlink.h>
  12
  13 struct Qdisc_ops;
  14 struct qdisc_walker;
  15 struct tcf_walker;
  16 struct module;
  17
  18 struct qdisc_rate_table
  19 {
  20         struct tc_ratespec rate;
  21         u32             data[256];
  22         struct qdisc_rate_table *next;
  23         int             refcnt;
  24 };
  25
  26 enum qdisc_state_t
  27 {
  28         __QDISC_STATE_RUNNING,
  29         __QDISC_STATE_SCHED,
  30         __QDISC_STATE_DEACTIVATED,
  31 };
  32
  33 struct qdisc_size_table {
  34         struct list_head        list;
  35         struct tc_sizespec      szopts;
  36         int                     refcnt;
  37         u16                     data[];
  38 };
  39
  40 struct Qdisc
  41 {
  42         int                     (*enqueue)(struct sk_buff *skb, struct Qdisc *dev);
  43         struct sk_buff *        (*dequeue)(struct Qdisc *dev);
  44         unsigned                flags;
  45 #define TCQ_F_BUILTIN           1
  46 #define TCQ_F_THROTTLED         2
  47 #define TCQ_F_INGRESS           4
  48 #define TCQ_F_WARN_NONWC        (1 << 16)
  49         int                     padded;
  50         struct Qdisc_ops        *ops;
  51         struct qdisc_size_table *stab;
  52         struct list_head        list;
  53         u32                     handle;
  54         u32                     parent;
  55         atomic_t                refcnt;
  56         struct gnet_stats_rate_est      rate_est;
  57         int                     (*reshape_fail)(struct sk_buff *skb,
  58                                         struct Qdisc *q);
  59
  60         void                    *u32_node;
  61
  62         /* This field is deprecated, but it is still used by CBQ
  63          * and it will live until better solution will be invented.
  64          */
  65         struct Qdisc            *__parent;
  66         struct netdev_queue     *dev_queue;
  67         struct Qdisc            *next_sched;
  68
  69         struct sk_buff          *gso_skb;
  70         /*
  71          * For performance sake on SMP, we put highly modified fields at the end
  72          */
  73         unsigned long           state;
  74         struct sk_buff_head     q;
  75         struct gnet_stats_basic bstats;
  76         struct gnet_stats_queue qstats;
  77 };
  78
  79 struct Qdisc_class_ops
  80 {
  81         /* Child qdisc manipulation */
  82         int                     (*graft)(struct Qdisc *, unsigned long cl,
  83                                         struct Qdisc *, struct Qdisc **);
  84         struct Qdisc *          (*leaf)(struct Qdisc *, unsigned long cl);
  85         void                    (*qlen_notify)(struct Qdisc *, unsigned long);
  86
  87         /* Class manipulation routines */
  88         unsigned long           (*get)(struct Qdisc *, u32 classid);
  89         void                    (*put)(struct Qdisc *, unsigned long);
  90         int                     (*change)(struct Qdisc *, u32, u32,
  91                                         struct nlattr **, unsigned long *);
  92         int                     (*delete)(struct Qdisc *, unsigned long);
  93         void                    (*walk)(struct Qdisc *, struct qdisc_walker * arg);
  94
  95         /* Filter manipulation */
  96         struct tcf_proto **     (*tcf_chain)(struct Qdisc *, unsigned long);
  97         unsigned long           (*bind_tcf)(struct Qdisc *, unsigned long,
  98                                         u32 classid);
  99         void                    (*unbind_tcf)(struct Qdisc *, unsigned long);
 100
 101         /* rtnetlink specific */
 102         int                     (*dump)(struct Qdisc *, unsigned long,
 103                                         struct sk_buff *skb, struct tcmsg*);
 104         int                     (*dump_stats)(struct Qdisc *, unsigned long,
 105                                         struct gnet_dump *);
 106 };
 107
 108 struct Qdisc_ops
 109 {
 110         struct Qdisc_ops        *next;
 111         const struct Qdisc_class_ops    *cl_ops;
 112         char                    id[IFNAMSIZ];
 113         int                     priv_size;
 114
 115         int                     (*enqueue)(struct sk_buff *, struct Qdisc *);
 116         struct sk_buff *        (*dequeue)(struct Qdisc *);
 117         struct sk_buff *        (*peek)(struct Qdisc *);
 118         unsigned int            (*drop)(struct Qdisc *);
 119
 120         int                     (*init)(struct Qdisc *, struct nlattr *arg);
 121         void                    (*reset)(struct Qdisc *);
 122         void                    (*destroy)(struct Qdisc *);
 123         int                     (*change)(struct Qdisc *, struct nlattr *arg);
 124
 125         int                     (*dump)(struct Qdisc *, struct sk_buff *);
 126         int                     (*dump_stats)(struct Qdisc *, struct gnet_dump *);
 127
 128         struct module           *owner;
 129 };
 130
 131
 132 struct tcf_result
 133 {
 134         unsigned long   class;
 135         u32             classid;
 136 };
 137
 138 struct tcf_proto_ops
 139 {
 140         struct tcf_proto_ops    *next;
 141         char                    kind[IFNAMSIZ];
 142
 143         int                     (*classify)(struct sk_buff*, struct tcf_proto*,
 144                                         struct tcf_result *);
 145         int                     (*init)(struct tcf_proto*);
 146         void                    (*destroy)(struct tcf_proto*);
 147
 148         unsigned long           (*get)(struct tcf_proto*, u32 handle);
 149         void                    (*put)(struct tcf_proto*, unsigned long);
 150         int                     (*change)(struct tcf_proto*, unsigned long,
 151                                         u32 handle, struct nlattr **,
 152                                         unsigned long *);
 153         int                     (*delete)(struct tcf_proto*, unsigned long);
 154         void                    (*walk)(struct tcf_proto*, struct tcf_walker *arg);
 155
 156         /* rtnetlink specific */
 157         int                     (*dump)(struct tcf_proto*, unsigned long,
 158                                         struct sk_buff *skb, struct tcmsg*);
 159
 160         struct module           *owner;
 161 };
 162
 163 struct tcf_proto
 164 {
 165         /* Fast access part */
 166         struct tcf_proto        *next;
 167         void                    *root;
 168         int                     (*classify)(struct sk_buff*, struct tcf_proto*,
 169                                         struct tcf_result *);
 170         __be16                  protocol;
 171
 172         /* All the rest */
 173         u32                     prio;
 174         u32                     classid;
 175         struct Qdisc            *q;
 176         void                    *data;
 177         struct tcf_proto_ops    *ops;
 178 };
 179
 180 struct qdisc_skb_cb {
 181         unsigned int            pkt_len;
 182         char                    data[];
 183 };
 184
 185 static inline struct qdisc_skb_cb *qdisc_skb_cb(struct sk_buff *skb)
 186 {
 187         return (struct qdisc_skb_cb *)skb->cb;
 188 }
 189
 190 static inline spinlock_t *qdisc_lock(struct Qdisc *qdisc)
 191 {
 192         return &qdisc->q.lock;
 193 }
 194
 195 static inline struct Qdisc *qdisc_root(struct Qdisc *qdisc)
 196 {
 197         return qdisc->dev_queue->qdisc;
 198 }
 199
 200 static inline struct Qdisc *qdisc_root_sleeping(struct Qdisc *qdisc)
 201 {
 202         return qdisc->dev_queue->qdisc_sleeping;
 203 }
 204
 205 /* The qdisc root lock is a mechanism by which to top level
 206  * of a qdisc tree can be locked from any qdisc node in the
 207  * forest.  This allows changing the configuration of some
 208  * aspect of the qdisc tree while blocking out asynchronous
 209  * qdisc access in the packet processing paths.
 210  *
 211  * It is only legal to do this when the root will not change
 212  * on us.  Otherwise we'll potentially lock the wrong qdisc
 213  * root.  This is enforced by holding the RTNL semaphore, which
 214  * all users of this lock accessor must do.
 215  */
 216 static inline spinlock_t *qdisc_root_lock(struct Qdisc *qdisc)
 217 {
 218         struct Qdisc *root = qdisc_root(qdisc);
 219
 220         ASSERT_RTNL();
 221         return qdisc_lock(root);
 222 }
 223
 224 static inline spinlock_t *qdisc_root_sleeping_lock(struct Qdisc *qdisc)
 225 {
 226         struct Qdisc *root = qdisc_root_sleeping(qdisc);
 227
 228         ASSERT_RTNL();
 229         return qdisc_lock(root);
 230 }
 231
 232 static inline struct net_device *qdisc_dev(struct Qdisc *qdisc)
 233 {
 234         return qdisc->dev_queue->dev;
 235 }
 236
 237 static inline void sch_tree_lock(struct Qdisc *q)
 238 {
 239         spin_lock_bh(qdisc_root_sleeping_lock(q));
 240 }
 241
 242 static inline void sch_tree_unlock(struct Qdisc *q)
 243 {
 244         spin_unlock_bh(qdisc_root_sleeping_lock(q));
 245 }
 246
 247 #define tcf_tree_lock(tp)       sch_tree_lock((tp)->q)
 248 #define tcf_tree_unlock(tp)     sch_tree_unlock((tp)->q)
 249
 250 extern struct Qdisc noop_qdisc;
 251 extern struct Qdisc_ops noop_qdisc_ops;
 252
 253 struct Qdisc_class_common
 254 {
 255         u32                     classid;
 256         struct hlist_node       hnode;
 257 };
 258
 259 struct Qdisc_class_hash
 260 {
 261         struct hlist_head       *hash;
 262         unsigned int            hashsize;
 263         unsigned int            hashmask;
 264         unsigned int            hashelems;
 265 };
 266
 267 static inline unsigned int qdisc_class_hash(u32 id, u32 mask)
 268 {
 269         id ^= id >> 8;
 270         id ^= id >> 4;
 271         return id & mask;
 272 }
 273
 274 static inline struct Qdisc_class_common *
 275 qdisc_class_find(struct Qdisc_class_hash *hash, u32 id)
 276 {
 277         struct Qdisc_class_common *cl;
 278         struct hlist_node *n;
 279         unsigned int h;
 280
 281         h = qdisc_class_hash(id, hash->hashmask);
 282         hlist_for_each_entry(cl, n, &hash->hash[h], hnode) {
 283                 if (cl->classid == id)
 284                         return cl;
 285         }
 286         return NULL;
 287 }
 288
 289 extern int qdisc_class_hash_init(struct Qdisc_class_hash *);
 290 extern void qdisc_class_hash_insert(struct Qdisc_class_hash *, struct Qdisc_class_common *);
 291 extern void qdisc_class_hash_remove(struct Qdisc_class_hash *, struct Qdisc_class_common *);
 292 extern void qdisc_class_hash_grow(struct Qdisc *, struct Qdisc_class_hash *);
 293 extern void qdisc_class_hash_destroy(struct Qdisc_class_hash *);
 294
 295 extern void dev_init_scheduler(struct net_device *dev);
 296 extern void dev_shutdown(struct net_device *dev);
 297 extern void dev_activate(struct net_device *dev);
 298 extern void dev_deactivate(struct net_device *dev);
 299 extern void qdisc_reset(struct Qdisc *qdisc);
 300 extern void qdisc_destroy(struct Qdisc *qdisc);
 301 extern void qdisc_tree_decrease_qlen(struct Qdisc *qdisc, unsigned int n);
 302 extern struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 303                                  struct Qdisc_ops *ops);
 304 extern struct Qdisc *qdisc_create_dflt(struct net_device *dev,
 305                                        struct netdev_queue *dev_queue,
 306                                        struct Qdisc_ops *ops, u32 parentid);
 307 extern void qdisc_calculate_pkt_len(struct sk_buff *skb,
 308                                    struct qdisc_size_table *stab);
 309 extern void tcf_destroy(struct tcf_proto *tp);
 310 extern void tcf_destroy_chain(struct tcf_proto **fl);
 311
 312 /* Reset all TX qdiscs of a device.  */
 313 static inline void qdisc_reset_all_tx(struct net_device *dev)
 314 {
 315         unsigned int i;
 316         for (i = 0; i < dev->num_tx_queues; i++)
 317                 qdisc_reset(netdev_get_tx_queue(dev, i)->qdisc);
 318 }
 319
 320 /* Are all TX queues of the device empty?  */
 321 static inline bool qdisc_all_tx_empty(const struct net_device *dev)
 322 {
 323         unsigned int i;
 324         for (i = 0; i < dev->num_tx_queues; i++) {
 325                 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 326                 const struct Qdisc *q = txq->qdisc;
 327
 328                 if (q->q.qlen)
 329                         return false;
 330         }
 331         return true;
 332 }
 333
 334 /* Are any of the TX qdiscs changing?  */
 335 static inline bool qdisc_tx_changing(struct net_device *dev)
 336 {
 337         unsigned int i;
 338         for (i = 0; i < dev->num_tx_queues; i++) {
 339                 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 340                 if (txq->qdisc != txq->qdisc_sleeping)
 341                         return true;
 342         }
 343         return false;
 344 }
 345
 346 /* Is the device using the noop qdisc on all queues?  */
 347 static inline bool qdisc_tx_is_noop(const struct net_device *dev)
 348 {
 349         unsigned int i;
 350         for (i = 0; i < dev->num_tx_queues; i++) {
 351                 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 352                 if (txq->qdisc != &noop_qdisc)
 353                         return false;
 354         }
 355         return true;
 356 }
 357
 358 static inline unsigned int qdisc_pkt_len(struct sk_buff *skb)
 359 {
 360         return qdisc_skb_cb(skb)->pkt_len;
 361 }
 362
 363 /* additional qdisc xmit flags (NET_XMIT_MASK in linux/netdevice.h) */
 364 enum net_xmit_qdisc_t {
 365         __NET_XMIT_STOLEN = 0x00010000,
 366         __NET_XMIT_BYPASS = 0x00020000,
 367 };
 368
 369 #ifdef CONFIG_NET_CLS_ACT
 370 #define net_xmit_drop_count(e)  ((e) & __NET_XMIT_STOLEN ? 0 : 1)
 371 #else
 372 #define net_xmit_drop_count(e)  (1)
 373 #endif
 374
 375 static inline int qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 376 {
 377 #ifdef CONFIG_NET_SCHED
 378         if (sch->stab)
 379                 qdisc_calculate_pkt_len(skb, sch->stab);
 380 #endif
 381         return sch->enqueue(skb, sch);
 382 }
 383
 384 static inline int qdisc_enqueue_root(struct sk_buff *skb, struct Qdisc *sch)
 385 {
 386         qdisc_skb_cb(skb)->pkt_len = skb->len;
 387         return qdisc_enqueue(skb, sch) & NET_XMIT_MASK;
 388 }
 389
 390 static inline int __qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch,
 391                                        struct sk_buff_head *list)
 392 {
 393         __skb_queue_tail(list, skb);
 394         sch->qstats.backlog += qdisc_pkt_len(skb);
 395         sch->bstats.bytes += qdisc_pkt_len(skb);
 396         sch->bstats.packets++;
 397
 398         return NET_XMIT_SUCCESS;
 399 }
 400
 401 static inline int qdisc_enqueue_tail(struct sk_buff *skb, struct Qdisc *sch)
 402 {
 403         return __qdisc_enqueue_tail(skb, sch, &sch->q);
 404 }
 405
 406 static inline struct sk_buff *__qdisc_dequeue_head(struct Qdisc *sch,
 407                                                    struct sk_buff_head *list)
 408 {
 409         struct sk_buff *skb = __skb_dequeue(list);
 410
 411         if (likely(skb != NULL))
 412                 sch->qstats.backlog -= qdisc_pkt_len(skb);
 413
 414         return skb;
 415 }
 416
 417 static inline struct sk_buff *qdisc_dequeue_head(struct Qdisc *sch)
 418 {
 419         return __qdisc_dequeue_head(sch, &sch->q);
 420 }
 421
 422 static inline struct sk_buff *__qdisc_dequeue_tail(struct Qdisc *sch,
 423                                                    struct sk_buff_head *list)
 424 {
 425         struct sk_buff *skb = __skb_dequeue_tail(list);
 426
 427         if (likely(skb != NULL))
 428                 sch->qstats.backlog -= qdisc_pkt_len(skb);
 429
 430         return skb;
 431 }
 432
 433 static inline struct sk_buff *qdisc_dequeue_tail(struct Qdisc *sch)
 434 {
 435         return __qdisc_dequeue_tail(sch, &sch->q);
 436 }
 437
 438 static inline struct sk_buff *qdisc_peek_head(struct Qdisc *sch)
 439 {
 440         return skb_peek(&sch->q);
 441 }
 442
 443 /* generic pseudo peek method for non-work-conserving qdisc */
 444 static inline struct sk_buff *qdisc_peek_dequeued(struct Qdisc *sch)
 445 {
 446         /* we can reuse ->gso_skb because peek isn't called for root qdiscs */
 447         if (!sch->gso_skb) {
 448                 sch->gso_skb = sch->dequeue(sch);
 449                 if (sch->gso_skb)
 450                         /* it's still part of the queue */
 451                         sch->q.qlen++;
 452         }
 453
 454         return sch->gso_skb;
 455 }
 456
 457 /* use instead of qdisc->dequeue() for all qdiscs queried with ->peek() */
 458 static inline struct sk_buff *qdisc_dequeue_peeked(struct Qdisc *sch)
 459 {
 460         struct sk_buff *skb = sch->gso_skb;
 461
 462         if (skb) {
 463                 sch->gso_skb = NULL;
 464                 sch->q.qlen--;
 465         } else {
 466                 skb = sch->dequeue(sch);
 467         }
 468
 469         return skb;
 470 }
 471
 472 static inline void __qdisc_reset_queue(struct Qdisc *sch,
 473                                        struct sk_buff_head *list)
 474 {
 475         /*
 476          * We do not know the backlog in bytes of this list, it
 477          * is up to the caller to correct it
 478          */
 479         __skb_queue_purge(list);
 480 }
 481
 482 static inline void qdisc_reset_queue(struct Qdisc *sch)
 483 {
 484         __qdisc_reset_queue(sch, &sch->q);
 485         sch->qstats.backlog = 0;
 486 }
 487
 488 static inline unsigned int __qdisc_queue_drop(struct Qdisc *sch,
 489                                               struct sk_buff_head *list)
 490 {
 491         struct sk_buff *skb = __qdisc_dequeue_tail(sch, list);
 492
 493         if (likely(skb != NULL)) {
 494                 unsigned int len = qdisc_pkt_len(skb);
 495                 kfree_skb(skb);
 496                 return len;
 497         }
 498
 499         return 0;
 500 }
 501
 502 static inline unsigned int qdisc_queue_drop(struct Qdisc *sch)
 503 {
 504         return __qdisc_queue_drop(sch, &sch->q);
 505 }
 506
 507 static inline int qdisc_drop(struct sk_buff *skb, struct Qdisc *sch)
 508 {
 509         kfree_skb(skb);
 510         sch->qstats.drops++;
 511
 512         return NET_XMIT_DROP;
 513 }
 514
 515 static inline int qdisc_reshape_fail(struct sk_buff *skb, struct Qdisc *sch)
 516 {
 517         sch->qstats.drops++;
 518
 519 #ifdef CONFIG_NET_CLS_ACT
 520         if (sch->reshape_fail == NULL || sch->reshape_fail(skb, sch))
 521                 goto drop;
 522
 523         return NET_XMIT_SUCCESS;
 524
 525 drop:
 526 #endif
 527         kfree_skb(skb);
 528         return NET_XMIT_DROP;
 529 }
 530
 531 /* Length to Time (L2T) lookup in a qdisc_rate_table, to determine how
 532    long it will take to send a packet given its size.
 533  */
 534 static inline u32 qdisc_l2t(struct qdisc_rate_table* rtab, unsigned int pktlen)
 535 {
 536         int slot = pktlen + rtab->rate.cell_align + rtab->rate.overhead;
 537         if (slot < 0)
 538                 slot = 0;
 539         slot >>= rtab->rate.cell_log;
 540         if (slot > 255)
 541                 return (rtab->data[255]*(slot >> 8) + rtab->data[slot & 0xFF]);
 542         return rtab->data[slot];
 543 }
 544
 545 #ifdef CONFIG_NET_CLS_ACT
 546 static inline struct sk_buff *skb_act_clone(struct sk_buff *skb, gfp_t gfp_mask)
 547 {
 548         struct sk_buff *n = skb_clone(skb, gfp_mask);
 549
 550         if (n) {
 551                 n->tc_verd = SET_TC_VERD(n->tc_verd, 0);
 552                 n->tc_verd = CLR_TC_OK2MUNGE(n->tc_verd);
 553                 n->tc_verd = CLR_TC_MUNGED(n->tc_verd);
 554         }
 555         return n;
 556 }
 557 #endif
 558
 559 #endif