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