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