include/net/pkt_sched.h

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