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