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