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 static inline int
 248 psched_tod_diff(int delta_sec, int bound)
 249 {
 250         int delta;
 251
 252         if (bound <= 1000000 || delta_sec > (0x7FFFFFFF/1000000)-1)
 253                 return bound;
 254         delta = delta_sec * 1000000;
 255         if (delta > bound)
 256                 delta = bound;
 257         return delta;
 258 }
 259
 260 #define PSCHED_TDIFF_SAFE(tv1, tv2, bound) \
 261 ({ \
 262            int __delta_sec = (tv1).tv_sec - (tv2).tv_sec; \
 263            int __delta = (tv1).tv_usec - (tv2).tv_usec; \
 264            switch (__delta_sec) { \
 265            default: \
 266                    __delta = psched_tod_diff(__delta_sec, bound);  break; \
 267            case 2: \
 268                    __delta += 1000000; \
 269            case 1: \
 270                    __delta += 1000000; \
 271            case 0: ; \
 272            } \
 273            __delta; \
 274 })
 275
 276 #define PSCHED_TLESS(tv1, tv2) (((tv1).tv_usec < (tv2).tv_usec && \
 277                                 (tv1).tv_sec <= (tv2).tv_sec) || \
 278                                  (tv1).tv_sec < (tv2).tv_sec)
 279
 280 #define PSCHED_TADD2(tv, delta, tv_res) \
 281 ({ \
 282            int __delta = (tv).tv_usec + (delta); \
 283            (tv_res).tv_sec = (tv).tv_sec; \
 284            if (__delta > 1000000) { (tv_res).tv_sec++; __delta -= 1000000; } \
 285            (tv_res).tv_usec = __delta; \
 286 })
 287
 288 #define PSCHED_TADD(tv, delta) \
 289 ({ \
 290            (tv).tv_usec += (delta); \
 291            if ((tv).tv_usec > 1000000) { (tv).tv_sec++; \
 292                  (tv).tv_usec -= 1000000; } \
 293 })
 294
 295 /* Set/check that time is in the "past perfect";
 296    it depends on concrete representation of system time
 297  */
 298
 299 #define PSCHED_SET_PASTPERFECT(t)       ((t).tv_sec = 0)
 300 #define PSCHED_IS_PASTPERFECT(t)        ((t).tv_sec == 0)
 301
 302 #define PSCHED_AUDIT_TDIFF(t) ({ if ((t) > 2000000) (t) = 2000000; })
 303
 304 #else /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 305
 306 #define PSCHED_TDIFF(tv1, tv2) (long)((tv1) - (tv2))
 307 #define PSCHED_TDIFF_SAFE(tv1, tv2, bound) \
 308         min_t(long long, (tv1) - (tv2), bound)
 309
 310
 311 #define PSCHED_TLESS(tv1, tv2) ((tv1) < (tv2))
 312 #define PSCHED_TADD2(tv, delta, tv_res) ((tv_res) = (tv) + (delta))
 313 #define PSCHED_TADD(tv, delta) ((tv) += (delta))
 314 #define PSCHED_SET_PASTPERFECT(t)       ((t) = 0)
 315 #define PSCHED_IS_PASTPERFECT(t)        ((t) == 0)
 316 #define PSCHED_AUDIT_TDIFF(t)
 317
 318 #endif /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */
 319
 320 struct tcf_police
 321 {
 322         struct tcf_police *next;
 323         int             refcnt;
 324 #ifdef CONFIG_NET_CLS_ACT
 325         int             bindcnt;
 326 #endif
 327         u32             index;
 328         int             action;
 329         int             result;
 330         u32             ewma_rate;
 331         u32             burst;
 332         u32             mtu;
 333         u32             toks;
 334         u32             ptoks;
 335         psched_time_t   t_c;
 336         spinlock_t      lock;
 337         struct qdisc_rate_table *R_tab;
 338         struct qdisc_rate_table *P_tab;
 339
 340         struct tc_stats stats;
 341         spinlock_t      *stats_lock;
 342 };
 343
 344 #ifdef CONFIG_NET_CLS_ACT
 345
 346 #define ACT_P_CREATED 1
 347 #define ACT_P_DELETED 1
 348 #define tca_gen(name) \
 349 struct tcf_##name *next; \
 350         u32 index; \
 351         int refcnt; \
 352         int bindcnt; \
 353         u32 capab; \
 354         int action; \
 355         struct tcf_t tm; \
 356         struct tc_stats stats; \
 357         spinlock_t *stats_lock; \
 358         spinlock_t lock
 359
 360
 361 struct tc_action
 362 {
 363         void *priv;
 364         struct tc_action_ops *ops;
 365         __u32   type;   /* for backward compat(TCA_OLD_COMPAT) */
 366         __u32   order;
 367         struct tc_action *next;
 368 };
 369
 370 #define TCA_CAP_NONE 0
 371 struct tc_action_ops
 372 {
 373         struct tc_action_ops *next;
 374         char    kind[IFNAMSIZ];
 375         __u32   type; /* TBD to match kind */
 376         __u32   capab;  /* capabilities includes 4 bit version */
 377         struct module           *owner;
 378         int     (*act)(struct sk_buff **, struct tc_action *);
 379         int     (*get_stats)(struct sk_buff *, struct tc_action *);
 380         int     (*dump)(struct sk_buff *, struct tc_action *,int , int);
 381         int     (*cleanup)(struct tc_action *, int bind);
 382         int     (*lookup)(struct tc_action *, u32 );
 383         int     (*init)(struct rtattr *,struct rtattr *,struct tc_action *, int , int );
 384         int     (*walk)(struct sk_buff *, struct netlink_callback *, int , struct tc_action *);
 385 };
 386
 387 extern int tcf_register_action(struct tc_action_ops *a);
 388 extern int tcf_unregister_action(struct tc_action_ops *a);
 389 extern void tcf_action_destroy(struct tc_action *a, int bind);
 390 extern int tcf_action_exec(struct sk_buff *skb, struct tc_action *a, struct tcf_result *res);
 391 extern int tcf_action_init(struct rtattr *rta, struct rtattr *est, struct tc_action *a,char *n, int ovr, int bind);
 392 extern int tcf_action_init_1(struct rtattr *rta, struct rtattr *est, struct tc_action *a,char *n, int ovr, int bind);
 393 extern int tcf_action_dump(struct sk_buff *skb, struct tc_action *a, int, int);
 394 extern int tcf_action_dump_old(struct sk_buff *skb, struct tc_action *a, int, int);
 395 extern int tcf_action_dump_1(struct sk_buff *skb, struct tc_action *a, int, int);
 396 extern int tcf_action_copy_stats (struct sk_buff *,struct tc_action *);
 397 extern int tcf_act_police_locate(struct rtattr *rta, struct rtattr *est,struct tc_action *,int , int );
 398 extern int tcf_act_police_dump(struct sk_buff *, struct tc_action *, int, int);
 399 extern int tcf_act_police(struct sk_buff **skb, struct tc_action *a);
 400 #endif
 401
 402 extern unsigned long tcf_set_class(struct tcf_proto *tp, unsigned long *clp,
 403                                    unsigned long cl);
 404 extern int tcf_police(struct sk_buff *skb, struct tcf_police *p);
 405 extern int qdisc_copy_stats(struct sk_buff *skb, struct tc_stats *st, spinlock_t *lock);
 406 extern void tcf_police_destroy(struct tcf_police *p);
 407 extern struct tcf_police * tcf_police_locate(struct rtattr *rta, struct rtattr *est);
 408 extern int tcf_police_dump(struct sk_buff *skb, struct tcf_police *p);
 409
 410 static inline int tcf_police_release(struct tcf_police *p, int bind)
 411 {
 412         int ret = 0;
 413 #ifdef CONFIG_NET_CLS_ACT
 414         if (p) {
 415                 if (bind) {
 416                          p->bindcnt--;
 417                 }
 418                 p->refcnt--;
 419                 if (p->refcnt <= 0 && !p->bindcnt) {
 420                         tcf_police_destroy(p);
 421                         ret = 1;
 422                 }
 423         }
 424 #else
 425         if (p && --p->refcnt == 0)
 426                 tcf_police_destroy(p);
 427
 428 #endif
 429         return ret;
 430 }
 431
 432 extern struct Qdisc noop_qdisc;
 433 extern struct Qdisc_ops noop_qdisc_ops;
 434 extern struct Qdisc_ops pfifo_qdisc_ops;
 435 extern struct Qdisc_ops bfifo_qdisc_ops;
 436
 437 int register_qdisc(struct Qdisc_ops *qops);
 438 int unregister_qdisc(struct Qdisc_ops *qops);
 439 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle);
 440 struct Qdisc *qdisc_lookup_class(struct net_device *dev, u32 handle);
 441 void dev_init_scheduler(struct net_device *dev);
 442 void dev_shutdown(struct net_device *dev);
 443 void dev_activate(struct net_device *dev);
 444 void dev_deactivate(struct net_device *dev);
 445 void qdisc_reset(struct Qdisc *qdisc);
 446 void qdisc_destroy(struct Qdisc *qdisc);
 447 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops);
 448 int qdisc_new_estimator(struct tc_stats *stats, spinlock_t *stats_lock, struct rtattr *opt);
 449 void qdisc_kill_estimator(struct tc_stats *stats);
 450 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct rtattr *tab);
 451 void qdisc_put_rtab(struct qdisc_rate_table *tab);
 452
 453 extern int qdisc_restart(struct net_device *dev);
 454
 455 /* Calculate maximal size of packet seen by hard_start_xmit
 456    routine of this device.
 457  */
 458 static inline unsigned psched_mtu(struct net_device *dev)
 459 {
 460         unsigned mtu = dev->mtu;
 461         return dev->hard_header ? mtu + dev->hard_header_len : mtu;
 462 }
 463
 464 #endif