include/net/pkt_sched.h

   1 #ifndef __NET_PKT_SCHED_H
   2 #define __NET_PKT_SCHED_H
   3
   4 #include <linux/config.h>
   5 #include <linux/netdevice.h>
   6 #include <linux/types.h>
   7 #include <linux/pkt_sched.h>
   8 #include <linux/rcupdate.h>
   9 #include <net/pkt_cls.h>
  10 #include <linux/module.h>
  11 #include <linux/rtnetlink.h>
  12
  13 struct rtattr;
  14 struct Qdisc;
  15
  16 struct qdisc_walker
  17 {
  18         int     stop;
  19         int     skip;
  20         int     count;
  21         int     (*fn)(struct Qdisc *, unsigned long cl, struct qdisc_walker *);
  22 };
  23
  24 struct Qdisc_class_ops
  25 {
  26         /* Child qdisc manipulation */
  27         int                     (*graft)(struct Qdisc *, unsigned long cl, struct Qdisc *, struct Qdisc **);
  28         struct Qdisc *          (*leaf)(struct Qdisc *, unsigned long cl);
  29
  30         /* Class manipulation routines */
  31         unsigned long           (*get)(struct Qdisc *, u32 classid);
  32         void                    (*put)(struct Qdisc *, unsigned long);
  33         int                     (*change)(struct Qdisc *, u32, u32, struct rtattr **, unsigned long *);
  34         int                     (*delete)(struct Qdisc *, unsigned long);
  35         void                    (*walk)(struct Qdisc *, struct qdisc_walker * arg);
  36
  37         /* Filter manipulation */
  38         struct tcf_proto **     (*tcf_chain)(struct Qdisc *, unsigned long);
  39         unsigned long           (*bind_tcf)(struct Qdisc *, unsigned long, u32 classid);
  40         void                    (*unbind_tcf)(struct Qdisc *, unsigned long);
  41
  42         /* rtnetlink specific */
  43         int                     (*dump)(struct Qdisc *, unsigned long, struct sk_buff *skb, struct tcmsg*);
  44 };
  45
  46 struct module;
  47
  48 struct Qdisc_ops
  49 {
  50         struct Qdisc_ops        *next;
  51         struct Qdisc_class_ops  *cl_ops;
  52         char                    id[IFNAMSIZ];
  53         int                     priv_size;
  54
  55         int                     (*enqueue)(struct sk_buff *, struct Qdisc *);
  56         struct sk_buff *        (*dequeue)(struct Qdisc *);
  57         int                     (*requeue)(struct sk_buff *, struct Qdisc *);
  58         unsigned int            (*drop)(struct Qdisc *);
  59
  60         int                     (*init)(struct Qdisc *, struct rtattr *arg);
  61         void                    (*reset)(struct Qdisc *);
  62         void                    (*destroy)(struct Qdisc *);
  63         int                     (*change)(struct Qdisc *, struct rtattr *arg);
  64
  65         int                     (*dump)(struct Qdisc *, struct sk_buff *);
  66
  67         struct module           *owner;
  68 };
  69
  70 extern rwlock_t qdisc_tree_lock;
  71
  72 struct Qdisc
  73 {
  74         int                     (*enqueue)(struct sk_buff *skb, struct Qdisc *dev);
  75         struct sk_buff *        (*dequeue)(struct Qdisc *dev);
  76         unsigned                flags;
  77 #define TCQ_F_BUILTIN   1
  78 #define TCQ_F_THROTTLED 2
  79 #define TCQ_F_INGRES    4
  80         int                     padded;
  81         struct Qdisc_ops        *ops;
  82         u32                     handle;
  83         atomic_t                refcnt;
  84         struct sk_buff_head     q;
  85         struct net_device       *dev;
  86         struct list_head        list;
  87
  88         struct tc_stats         stats;
  89         spinlock_t              *stats_lock;
  90         struct rcu_head         q_rcu;
  91         int                     (*reshape_fail)(struct sk_buff *skb, struct Qdisc *q);
  92
  93         /* This field is deprecated, but it is still used by CBQ
  94          * and it will live until better solution will be invented.
  95          */
  96         struct Qdisc            *__parent;
  97 };
  98
  99 #define QDISC_ALIGN             32
 100 #define QDISC_ALIGN_CONST       (QDISC_ALIGN - 1)
 101
 102 static inline void *qdisc_priv(struct Qdisc *q)
 103 {
 104         return (char *)q + ((sizeof(struct Qdisc) + QDISC_ALIGN_CONST)
 105                               & ~QDISC_ALIGN_CONST);
 106 }
 107
 108 struct qdisc_rate_table
 109 {
 110         struct tc_ratespec rate;
 111         u32             data[256];
 112         struct qdisc_rate_table *next;
 113         int             refcnt;
 114 };
 115
 116 extern void qdisc_lock_tree(struct net_device *dev);
 117 extern void qdisc_unlock_tree(struct net_device *dev);
 118
 119 #define sch_tree_lock(q)        qdisc_lock_tree((q)->dev)
 120 #define sch_tree_unlock(q)      qdisc_unlock_tree((q)->dev)
 121 #define tcf_tree_lock(tp)       qdisc_lock_tree((tp)->q->dev)
 122 #define tcf_tree_unlock(tp)     qdisc_unlock_tree((tp)->q->dev)
 123
 124 #define cls_set_class(tp, clp, cl) tcf_set_class(tp, clp, cl)
 125 static inline unsigned long
 126 __cls_set_class(unsigned long *clp, unsigned long cl)
 127 {
 128         unsigned long old_cl;
 129
 130         old_cl = *clp;
 131         *clp = cl;
 132         return old_cl;
 133 }
 134
 135
 136 /*
 137    Timer resolution MUST BE < 10% of min_schedulable_packet_size/bandwidth
 138
 139    Normal IP packet size ~ 512byte, hence:
 140
 141    0.5Kbyte/1Mbyte/sec = 0.5msec, so that we need 50usec timer for
 142    10Mbit ethernet.
 143
 144    10msec resolution -> <50Kbit/sec.
 145
 146    The result: [34]86 is not good choice for QoS router :-(
 147
 148    The things are not so bad, because we may use artifical
 149    clock evaluated by integration of network data flow
 150    in the most critical places.
 151
 152    Note: we do not use fastgettimeofday.
 153    The reason is that, when it is not the same thing as
 154    gettimeofday, it returns invalid timestamp, which is
 155    not updated, when net_bh is active.
 156  */
 157
 158 /* General note about internal clock.
 159
 160    Any clock source returns time intervals, measured in units
 161    close to 1usec. With source CONFIG_NET_SCH_CLK_GETTIMEOFDAY it is precisely
 162    microseconds, otherwise something close but different chosen to minimize
 163    arithmetic cost. Ratio usec/internal untis in form nominator/denominator
 164    may be read from /proc/net/psched.
 165  */
 166
 167
 168 #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
 169
 170 typedef struct timeval  psched_time_t;
 171 typedef long            psched_tdiff_t;
 172
 173 #define PSCHED_GET_TIME(stamp) do_gettimeofday(&(stamp))
 174 #define PSCHED_US2JIFFIE(usecs) (((usecs)+(1000000/HZ-1))/(1000000/HZ))
 175 #define PSCHED_JIFFIE2US(delay) ((delay)*(1000000/HZ))
 176
 177 #else /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 178
 179 typedef u64     psched_time_t;
 180 typedef long    psched_tdiff_t;
 181
 182 #ifdef CONFIG_NET_SCH_CLK_JIFFIES
 183
 184 #if HZ < 96
 185 #define PSCHED_JSCALE 14
 186 #elif HZ >= 96 && HZ < 192
 187 #define PSCHED_JSCALE 13
 188 #elif HZ >= 192 && HZ < 384
 189 #define PSCHED_JSCALE 12
 190 #elif HZ >= 384 && HZ < 768
 191 #define PSCHED_JSCALE 11
 192 #elif HZ >= 768
 193 #define PSCHED_JSCALE 10
 194 #endif
 195
 196 #define PSCHED_GET_TIME(stamp) ((stamp) = (get_jiffies_64()<<PSCHED_JSCALE))
 197 #define PSCHED_US2JIFFIE(delay) (((delay)+(1<<PSCHED_JSCALE)-1)>>PSCHED_JSCALE)
 198 #define PSCHED_JIFFIE2US(delay) ((delay)<<PSCHED_JSCALE)
 199
 200 #endif /* CONFIG_NET_SCH_CLK_JIFFIES */
 201 #ifdef CONFIG_NET_SCH_CLK_CPU
 202 #include <asm/timex.h>
 203
 204 extern psched_tdiff_t psched_clock_per_hz;
 205 extern int psched_clock_scale;
 206 extern psched_time_t psched_time_base;
 207 extern cycles_t psched_time_mark;
 208
 209 #define PSCHED_GET_TIME(stamp)                                          \
 210 do {                                                                    \
 211         cycles_t cur = get_cycles();                                    \
 212         if (sizeof(cycles_t) == sizeof(u32)) {                          \
 213                 if (cur <= psched_time_mark)                            \
 214                         psched_time_base += 0x100000000ULL;             \
 215                 psched_time_mark = cur;                                 \
 216                 (stamp) = (psched_time_base + cur)>>psched_clock_scale; \
 217         } else {                                                        \
 218                 (stamp) = cur>>psched_clock_scale;                      \
 219         }                                                               \
 220 } while (0)
 221 #define PSCHED_US2JIFFIE(delay) (((delay)+psched_clock_per_hz-1)/psched_clock_per_hz)
 222 #define PSCHED_JIFFIE2US(delay) ((delay)*psched_clock_per_hz)
 223
 224 #endif /* CONFIG_NET_SCH_CLK_CPU */
 225
 226 #endif /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 227
 228 #ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY
 229 #define PSCHED_TDIFF(tv1, tv2) \
 230 ({ \
 231            int __delta_sec = (tv1).tv_sec - (tv2).tv_sec; \
 232            int __delta = (tv1).tv_usec - (tv2).tv_usec; \
 233            if (__delta_sec) { \
 234                    switch (__delta_sec) { \
 235                    default: \
 236                            __delta = 0; \
 237                    case 2: \
 238                            __delta += 1000000; \
 239                    case 1: \
 240                            __delta += 1000000; \
 241                    } \
 242            } \
 243            __delta; \
 244 })
 245
 246 extern int psched_tod_diff(int delta_sec, int bound);
 247
 248 #define PSCHED_TDIFF_SAFE(tv1, tv2, bound) \
 249 ({ \
 250            int __delta_sec = (tv1).tv_sec - (tv2).tv_sec; \
 251            int __delta = (tv1).tv_usec - (tv2).tv_usec; \
 252            switch (__delta_sec) { \
 253            default: \
 254                    __delta = psched_tod_diff(__delta_sec, bound);  break; \
 255            case 2: \
 256                    __delta += 1000000; \
 257            case 1: \
 258                    __delta += 1000000; \
 259            case 0: ; \
 260            } \
 261            __delta; \
 262 })
 263
 264 #define PSCHED_TLESS(tv1, tv2) (((tv1).tv_usec < (tv2).tv_usec && \
 265                                 (tv1).tv_sec <= (tv2).tv_sec) || \
 266                                  (tv1).tv_sec < (tv2).tv_sec)
 267
 268 #define PSCHED_TADD2(tv, delta, tv_res) \
 269 ({ \
 270            int __delta = (tv).tv_usec + (delta); \
 271            (tv_res).tv_sec = (tv).tv_sec; \
 272            if (__delta > 1000000) { (tv_res).tv_sec++; __delta -= 1000000; } \
 273            (tv_res).tv_usec = __delta; \
 274 })
 275
 276 #define PSCHED_TADD(tv, delta) \
 277 ({ \
 278            (tv).tv_usec += (delta); \
 279            if ((tv).tv_usec > 1000000) { (tv).tv_sec++; \
 280                  (tv).tv_usec -= 1000000; } \
 281 })
 282
 283 /* Set/check that time is in the "past perfect";
 284    it depends on concrete representation of system time
 285  */
 286
 287 #define PSCHED_SET_PASTPERFECT(t)       ((t).tv_sec = 0)
 288 #define PSCHED_IS_PASTPERFECT(t)        ((t).tv_sec == 0)
 289
 290 #define PSCHED_AUDIT_TDIFF(t) ({ if ((t) > 2000000) (t) = 2000000; })
 291
 292 #else /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 293
 294 #define PSCHED_TDIFF(tv1, tv2) (long)((tv1) - (tv2))
 295 #define PSCHED_TDIFF_SAFE(tv1, tv2, bound) \
 296         min_t(long long, (tv1) - (tv2), bound)
 297
 298
 299 #define PSCHED_TLESS(tv1, tv2) ((tv1) < (tv2))
 300 #define PSCHED_TADD2(tv, delta, tv_res) ((tv_res) = (tv) + (delta))
 301 #define PSCHED_TADD(tv, delta) ((tv) += (delta))
 302 #define PSCHED_SET_PASTPERFECT(t)       ((t) = 0)
 303 #define PSCHED_IS_PASTPERFECT(t)        ((t) == 0)
 304 #define PSCHED_AUDIT_TDIFF(t)
 305
 306 #endif /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 307
 308 struct tcf_police
 309 {
 310         struct tcf_police *next;
 311         int             refcnt;
 312 #ifdef CONFIG_NET_CLS_ACT
 313         int             bindcnt;
 314 #endif
 315         u32             index;
 316         int             action;
 317         int             result;
 318         u32             ewma_rate;
 319         u32             burst;
 320         u32             mtu;
 321         u32             toks;
 322         u32             ptoks;
 323         psched_time_t   t_c;
 324         spinlock_t      lock;
 325         struct qdisc_rate_table *R_tab;
 326         struct qdisc_rate_table *P_tab;
 327
 328         struct tc_stats stats;
 329         spinlock_t      *stats_lock;
 330 };
 331
 332 #ifdef CONFIG_NET_CLS_ACT
 333
 334 #define ACT_P_CREATED 1
 335 #define ACT_P_DELETED 1
 336 #define tca_gen(name) \
 337 struct tcf_##name *next; \
 338         u32 index; \
 339         int refcnt; \
 340         int bindcnt; \
 341         u32 capab; \
 342         int action; \
 343         struct tcf_t tm; \
 344         struct tc_stats stats; \
 345         spinlock_t *stats_lock; \
 346         spinlock_t lock
 347
 348
 349 struct tc_action
 350 {
 351         void *priv;
 352         struct tc_action_ops *ops;
 353         __u32   type;   /* for backward compat(TCA_OLD_COMPAT) */
 354         __u32   order;
 355         struct tc_action *next;
 356 };
 357
 358 #define TCA_CAP_NONE 0
 359 struct tc_action_ops
 360 {
 361         struct tc_action_ops *next;
 362         char    kind[IFNAMSIZ];
 363         __u32   type; /* TBD to match kind */
 364         __u32   capab;  /* capabilities includes 4 bit version */
 365         struct module           *owner;
 366         int     (*act)(struct sk_buff **, struct tc_action *);
 367         int     (*get_stats)(struct sk_buff *, struct tc_action *);
 368         int     (*dump)(struct sk_buff *, struct tc_action *,int , int);
 369         int     (*cleanup)(struct tc_action *, int bind);
 370         int     (*lookup)(struct tc_action *, u32 );
 371         int     (*init)(struct rtattr *,struct rtattr *,struct tc_action *, int , int );
 372         int     (*walk)(struct sk_buff *, struct netlink_callback *, int , struct tc_action *);
 373 };
 374
 375 extern int tcf_register_action(struct tc_action_ops *a);
 376 extern int tcf_unregister_action(struct tc_action_ops *a);
 377 extern void tcf_action_destroy(struct tc_action *a, int bind);
 378 extern int tcf_action_exec(struct sk_buff *skb, struct tc_action *a);
 379 extern int tcf_action_init(struct rtattr *rta, struct rtattr *est, struct tc_action *a,char *n, int ovr, int bind);
 380 extern int tcf_action_init_1(struct rtattr *rta, struct rtattr *est, struct tc_action *a,char *n, int ovr, int bind);
 381 extern int tcf_action_dump(struct sk_buff *skb, struct tc_action *a, int, int);
 382 extern int tcf_action_dump_old(struct sk_buff *skb, struct tc_action *a, int, int);
 383 extern int tcf_action_dump_1(struct sk_buff *skb, struct tc_action *a, int, int);
 384 extern int tcf_action_copy_stats (struct sk_buff *,struct tc_action *);
 385 extern int tcf_act_police_locate(struct rtattr *rta, struct rtattr *est,struct tc_action *,int , int );
 386 extern int tcf_act_police_dump(struct sk_buff *, struct tc_action *, int, int);
 387 extern int tcf_act_police(struct sk_buff **skb, struct tc_action *a);
 388 #endif
 389
 390 extern unsigned long tcf_set_class(struct tcf_proto *tp, unsigned long *clp,
 391                                    unsigned long cl);
 392 extern int tcf_police(struct sk_buff *skb, struct tcf_police *p);
 393 extern int qdisc_copy_stats(struct sk_buff *skb, struct tc_stats *st, spinlock_t *lock);
 394 extern void tcf_police_destroy(struct tcf_police *p);
 395 extern struct tcf_police * tcf_police_locate(struct rtattr *rta, struct rtattr *est);
 396 extern int tcf_police_dump(struct sk_buff *skb, struct tcf_police *p);
 397
 398 static inline int tcf_police_release(struct tcf_police *p, int bind)
 399 {
 400         int ret = 0;
 401 #ifdef CONFIG_NET_CLS_ACT
 402         if (p) {
 403                 if (bind) {
 404                          p->bindcnt--;
 405                 }
 406                 p->refcnt--;
 407                 if (p->refcnt <= 0 && !p->bindcnt) {
 408                         tcf_police_destroy(p);
 409                         ret = 1;
 410                 }
 411         }
 412 #else
 413         if (p && --p->refcnt == 0)
 414                 tcf_police_destroy(p);
 415
 416 #endif
 417         return ret;
 418 }
 419
 420 extern struct Qdisc noop_qdisc;
 421 extern struct Qdisc_ops noop_qdisc_ops;
 422 extern struct Qdisc_ops pfifo_qdisc_ops;
 423 extern struct Qdisc_ops bfifo_qdisc_ops;
 424
 425 int register_qdisc(struct Qdisc_ops *qops);
 426 int unregister_qdisc(struct Qdisc_ops *qops);
 427 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle);
 428 struct Qdisc *qdisc_lookup_class(struct net_device *dev, u32 handle);
 429 void dev_init_scheduler(struct net_device *dev);
 430 void dev_shutdown(struct net_device *dev);
 431 void dev_activate(struct net_device *dev);
 432 void dev_deactivate(struct net_device *dev);
 433 void qdisc_reset(struct Qdisc *qdisc);
 434 void qdisc_destroy(struct Qdisc *qdisc);
 435 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops);
 436 int qdisc_new_estimator(struct tc_stats *stats, spinlock_t *stats_lock, struct rtattr *opt);
 437 void qdisc_kill_estimator(struct tc_stats *stats);
 438 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct rtattr *tab);
 439 void qdisc_put_rtab(struct qdisc_rate_table *tab);
 440
 441 extern int qdisc_restart(struct net_device *dev);
 442
 443 /* Calculate maximal size of packet seen by hard_start_xmit
 444    routine of this device.
 445  */
 446 static inline unsigned psched_mtu(struct net_device *dev)
 447 {
 448         unsigned mtu = dev->mtu;
 449         return dev->hard_header ? mtu + dev->hard_header_len : mtu;
 450 }
 451
 452 #endif