bsd/net/pktsched/pktsched_rmclass.h

   1 /*
   2  * Copyright (c) 2011 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /* $OpenBSD: altq_rmclass.h,v 1.10 2007/06/17 19:58:58 jasper Exp $     */
  30 /* $KAME: altq_rmclass.h,v 1.6 2000/12/09 09:22:44 kjc Exp $    */
  31
  32 /*
  33  * Copyright (c) 1991-1997 Regents of the University of California.
  34  * All rights reserved.
  35  *
  36  * Redistribution and use in source and binary forms, with or without
  37  * modification, are permitted provided that the following conditions
  38  * are met:
  39  * 1. Redistributions of source code must retain the above copyright
  40  *    notice, this list of conditions and the following disclaimer.
  41  * 2. Redistributions in binary form must reproduce the above copyright
  42  *    notice, this list of conditions and the following disclaimer in the
  43  *    documentation and/or other materials provided with the distribution.
  44  * 3. All advertising materials mentioning features or use of this software
  45  *    must display the following acknowledgement:
  46  *      This product includes software developed by the Network Research
  47  *      Group at Lawrence Berkeley Laboratory.
  48  * 4. Neither the name of the University nor of the Laboratory may be used
  49  *    to endorse or promote products derived from this software without
  50  *    specific prior written permission.
  51  *
  52  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  53  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  54  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  55  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  56  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  57  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  58  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  59  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  60  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  61  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  62  * SUCH DAMAGE.
  63  */
  64
  65 #ifndef _NET_PKTSCHED_PKTSCHED_RMCLASS_H_
  66 #define _NET_PKTSCHED_PKTSCHED_RMCLASS_H_
  67
  68 #ifdef PRIVATE
  69 #include <net/classq/classq.h>
  70 #include <net/pktsched/pktsched.h>
  71
  72 #ifdef __cplusplus
  73 extern "C" {
  74 #endif
  75
  76 #define RM_MAXPRIO      8       /* Max priority */
  77
  78 /* flags for rmc_init and rmc_newclass */
  79 /* class flags */
  80 #define RMCF_RED                0x0001  /* use RED */
  81 #define RMCF_ECN                0x0002  /* use ECN with RED/BLUE/SFB */
  82 #define RMCF_RIO                0x0004  /* use RIO */
  83 #define RMCF_FLOWVALVE          0x0008  /* use flowvalve (aka penalty-box) */
  84 #define RMCF_CLEARDSCP          0x0010  /* clear diffserv codepoint */
  85
  86 /* flags for rmc_init */
  87 #define RMCF_WRR                0x0100
  88 #define RMCF_EFFICIENT          0x0200
  89
  90 #define RMCF_BLUE               0x10000 /* use BLUE */
  91 #define RMCF_SFB                0x20000 /* use SFB */
  92 #define RMCF_FLOWCTL            0x40000 /* enable flow control advisories */
  93 #ifdef BSD_KERNEL_PRIVATE
  94 #define RMCF_LAZY               0x10000000 /* on-demand resource allocation */
  95
  96 typedef struct rm_ifdat         rm_ifdat_t;
  97 typedef struct rm_class         rm_class_t;
  98
  99 struct red;
 100 struct rio;
 101 struct blue;
 102 struct sfb;
 103
 104 /*
 105  * Macros for dealing with time values.  We assume all times are
 106  * 'timevals'.  `microuptime' is used to get the best available clock
 107  * resolution.  If `microuptime' *doesn't* return a value that's about
 108  * ten times smaller than the average packet time on the fastest
 109  * link that will use these routines, a slightly different clock
 110  * scheme than this one should be used.
 111  * (Bias due to truncation error in this scheme will overestimate utilization
 112  * and discriminate against high bandwidth classes.  To remove this bias an
 113  * integrator needs to be added.  The simplest integrator uses a history of
 114  * 10 * avg.packet.time / min.tick.time packet completion entries.  This is
 115  * straight forward to add but we don't want to pay the extra memory
 116  * traffic to maintain it if it's not necessary (occasionally a vendor
 117  * accidentally builds a workstation with a decent clock - e.g., Sun & HP).)
 118  */
 119
 120 #define RM_GETTIME(now) microuptime(&now)
 121
 122 #define TV_LT(a, b) (((a)->tv_sec < (b)->tv_sec) ||  \
 123         (((a)->tv_usec < (b)->tv_usec) && ((a)->tv_sec <= (b)->tv_sec)))
 124
 125 #define TV_DELTA(a, b, delta) {                                         \
 126         int     xxs;                                                    \
 127                                                                         \
 128         delta = (a)->tv_usec - (b)->tv_usec;                            \
 129         if ((xxs = (a)->tv_sec - (b)->tv_sec)) {                        \
 130                 switch (xxs) {                                          \
 131                 default:                                                \
 132                         /*                                              \
 133                          * if (xxs < 0)                                 \
 134                          *      printf("rm_class: bogus time values\n"); \
 135                          */                                             \
 136                         delta = 0;                                      \
 137                         /* fall through */                              \
 138                 case 2:                                                 \
 139                         delta += 1000000;                               \
 140                         /* fall through */                              \
 141                 case 1:                                                 \
 142                         delta += 1000000;                               \
 143                         break;                                          \
 144                 }                                                       \
 145         }                                                               \
 146 }
 147
 148 #define TV_ADD_DELTA(a, delta, res) {                                   \
 149         int xxus = (a)->tv_usec + (delta);                              \
 150                                                                         \
 151         (res)->tv_sec = (a)->tv_sec;                                    \
 152         while (xxus >= 1000000) {                                       \
 153                 ++((res)->tv_sec);                                      \
 154                 xxus -= 1000000;                                        \
 155         }                                                               \
 156         (res)->tv_usec = xxus;                                          \
 157 }
 158
 159 #define RM_TIMEOUT      2       /* 1 Clock tick. */
 160
 161 #if 1
 162 #define RM_MAXQUEUED    1       /* this isn't used in ALTQ/CBQ */
 163 #else
 164 #define RM_MAXQUEUED    16      /* Max number of packets downstream of CBQ */
 165 #endif
 166 #define RM_MAXQUEUE     64      /* Max queue length */
 167 #define RM_FILTER_GAIN  5       /* log2 of gain, e.g., 5 => 31/32 */
 168 #define RM_POWER        (1 << RM_FILTER_GAIN)
 169 #define RM_MAXDEPTH     32
 170 #define RM_NS_PER_SEC   (1000000000)
 171
 172 typedef struct _rm_class_stats_ {
 173         u_int32_t       handle;
 174         u_int32_t       depth;
 175
 176         struct pktcntr  xmit_cnt;       /* packets sent in this class */
 177         struct pktcntr  drop_cnt;       /* dropped packets */
 178         u_int32_t       over;           /* # times went over limit */
 179         u_int32_t       borrows;        /* # times tried to borrow */
 180         u_int32_t       overactions;    /* # times invoked overlimit action */
 181         u_int32_t       delays;         /* # times invoked delay actions */
 182 } rm_class_stats_t;
 183
 184 /*
 185  * CBQ Class state structure
 186  */
 187 struct rm_class {
 188         class_queue_t   q_;             /* Queue of packets */
 189         rm_ifdat_t      *ifdat_;
 190         int             pri_;           /* Class priority. */
 191         int             depth_;         /* Class depth */
 192         u_int32_t       ns_per_byte_;   /* NanoSeconds per byte. */
 193         u_int32_t       maxrate_;       /* Bytes per second for this class. */
 194         u_int32_t       allotment_;     /* Fraction of link bandwidth. */
 195         u_int32_t       w_allotment_;   /* Weighted allotment for WRR */
 196         int             bytes_alloc_;   /* Allocation for round of WRR */
 197
 198         int             avgidle_;
 199         int             maxidle_;
 200         int             minidle_;
 201         int             offtime_;
 202         int             sleeping_;      /* != 0 if delaying */
 203         u_int32_t       qthresh_;       /* Threshold for formal link sharing */
 204         int             leaf_;          /* Note whether leaf class or not */
 205
 206         rm_class_t      *children_;     /* Children of this class */
 207         rm_class_t      *next_;         /* Next pointer, used if child */
 208
 209         rm_class_t      *peer_;         /* Peer class */
 210         rm_class_t      *borrow_;       /* Borrow class */
 211         rm_class_t      *parent_;       /* Parent class */
 212
 213         void    (*overlimit)(struct rm_class *, struct rm_class *);
 214         void    (*drop)(struct rm_class *); /* Class drop action. */
 215
 216         union {
 217                 void            *ptr;
 218                 struct red      *red;   /* RED state */
 219                 struct rio      *rio;   /* RIO state */
 220                 struct blue     *blue;  /* BLUE state */
 221                 struct sfb      *sfb;   /* SFB state */
 222         } qalg_;
 223         int             flags_;
 224         u_int32_t       qflags_;
 225
 226         int             last_pkttime_;  /* saved pkt_time */
 227         struct timeval  undertime_;     /* time can next send */
 228         struct timeval  last_;          /* time last packet sent */
 229         struct timeval  overtime_;
 230         struct callout  callout_;       /* for timeout() calls */
 231
 232         rm_class_stats_t stats_;        /* Class Statistics */
 233 };
 234
 235 #define red_    qalg_.red
 236 #define rio_    qalg_.rio
 237 #define blue_   qalg_.blue
 238 #define sfb_    qalg_.sfb
 239
 240 /*
 241  * CBQ Interface state
 242  */
 243 struct rm_ifdat {
 244         int             queued_;        /* # pkts queued downstream */
 245         int             efficient_;     /* Link Efficency bit */
 246         int             wrr_;           /* Enable Weighted Round-Robin */
 247         u_long          ns_per_byte_;   /* Link byte speed. */
 248         int             maxqueued_;     /* Max packets to queue */
 249         int             maxpkt_;        /* Max packet size. */
 250         int             qi_;            /* In/out pointers for downstream */
 251         int             qo_;            /* packets */
 252
 253         /*
 254          * Active class state and WRR state.
 255          */
 256         rm_class_t      *active_[RM_MAXPRIO];   /* Active cl's in each pri */
 257         int             na_[RM_MAXPRIO];        /* # of active cl's in a pri */
 258         int             num_[RM_MAXPRIO];       /* # of cl's per pri */
 259         int             alloc_[RM_MAXPRIO];     /* Byte Allocation */
 260         u_long          M_[RM_MAXPRIO];         /* WRR weights. */
 261
 262         /*
 263          * Network Interface/Solaris Queue state pointer.
 264          */
 265         struct ifclassq *ifq_;
 266         rm_class_t      *default_;      /* Default Pkt class, BE */
 267         rm_class_t      *root_;         /* Root Link class. */
 268         rm_class_t      *ctl_;          /* Control Traffic class. */
 269         void            (*restart)(struct ifclassq *);  /* Restart routine. */
 270
 271         /*
 272          * Current packet downstream packet state and dynamic state.
 273          */
 274         rm_class_t      *borrowed_[RM_MAXQUEUED]; /* Class borrowed last */
 275         rm_class_t      *class_[RM_MAXQUEUED];  /* class sending */
 276         int             curlen_[RM_MAXQUEUED];  /* Current pktlen */
 277         struct timeval  now_[RM_MAXQUEUED];     /* Current packet time */
 278         int             is_overlimit_[RM_MAXQUEUED]; /* Current packet time */
 279
 280         int             cutoff_;        /* Cut-off depth for borrowing */
 281
 282         struct timeval  ifnow_;         /* expected xmit completion time */
 283 #if 1 /* ALTQ4PPP */
 284         int             maxiftime_;     /* max delay inside interface */
 285 #endif
 286         rm_class_t      *pollcache_;    /* cached rm_class by poll operation */
 287 };
 288
 289 #define RMC_IS_A_PARENT_CLASS(cl)       ((cl)->children_ != NULL)
 290
 291 extern void rmclass_init(void);
 292 extern rm_class_t *rmc_newclass(int, struct rm_ifdat *, u_int32_t,
 293     void (*)(struct rm_class *, struct rm_class *), u_int32_t,
 294     u_int32_t, struct rm_class *, struct rm_class *,
 295     u_int32_t, int, u_int32_t, int, int);
 296 extern void rmc_delete_class(struct rm_ifdat *, struct rm_class *);
 297 extern int rmc_modclass(struct rm_class *, u_int32_t, int, u_int32_t,
 298     int, u_int32_t, int);
 299 extern int rmc_init(struct ifclassq *, struct rm_ifdat *, u_int32_t,
 300     void (*)(struct ifclassq *), u_int32_t, int, int, u_int32_t,
 301     int, u_int32_t, int);
 302 extern int rmc_queue_packet(struct rm_class *, struct mbuf *, struct pf_mtag *);
 303 extern struct mbuf *rmc_dequeue_next(struct rm_ifdat *, cqdq_op_t);
 304 extern void rmc_update_class_util(struct rm_ifdat *);
 305 extern void rmc_delay_action(struct rm_class *, struct rm_class *);
 306 extern void rmc_drop(struct rm_class *, u_int32_t, u_int32_t *, u_int32_t *);
 307 extern void rmc_dropall(struct rm_class *);
 308 extern int rmc_get_weight(struct rm_ifdat *, int);
 309 extern void rmc_updateq(struct rm_class *, cqev_t);
 310
 311 #endif /* BSD_KERNEL_PRIVATE */
 312
 313 #ifdef __cplusplus
 314 }
 315 #endif
 316 #endif /* PRIVATE */
 317 #endif /* _NET_PKTSCHED_PKTSCHED_RMCLASS_H_ */