bsd/net/pktsched/pktsched_hfsc.h

   1 /*
   2  * Copyright (c) 2011-2012 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 /*      $NetBSD: altq_hfsc.h,v 1.8 2006/10/12 19:59:08 peter Exp $      */
  30 /*      $KAME: altq_hfsc.h,v 1.12 2003/12/05 05:40:46 kjc Exp $ */
  31
  32 /*
  33  * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
  34  *
  35  * Permission to use, copy, modify, and distribute this software and
  36  * its documentation is hereby granted (including for commercial or
  37  * for-profit use), provided that both the copyright notice and this
  38  * permission notice appear in all copies of the software, derivative
  39  * works, or modified versions, and any portions thereof.
  40  *
  41  * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
  42  * WHICH MAY HAVE SERIOUS CONSEQUENCES.  CARNEGIE MELLON PROVIDES THIS
  43  * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
  44  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  45  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  46  * DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  47  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  48  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  49  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  50  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  51  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  52  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  53  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  54  * DAMAGE.
  55  *
  56  * Carnegie Mellon encourages (but does not require) users of this
  57  * software to return any improvements or extensions that they make,
  58  * and to grant Carnegie Mellon the rights to redistribute these
  59  * changes without encumbrance.
  60  */
  61 #ifndef _NET_PKTSCHED_PKTSCHED_HFSC_H_
  62 #define _NET_PKTSCHED_PKTSCHED_HFSC_H_
  63
  64 #ifdef PRIVATE
  65 #include <net/pktsched/pktsched.h>
  66 #include <net/classq/classq.h>
  67 #include <net/classq/classq_red.h>
  68 #include <net/classq/classq_rio.h>
  69 #include <net/classq/classq_blue.h>
  70 #include <net/classq/classq_sfb.h>
  71
  72 #ifdef __cplusplus
  73 extern "C" {
  74 #endif
  75
  76 struct service_curve {
  77         u_int32_t fl;   /* service curve flags */
  78         u_int64_t m1;   /* slope of the first segment in bits/sec */
  79         u_int32_t d;    /* the x-projection of the first segment in msec */
  80         u_int64_t m2;   /* slope of the second segment in bits/sec */
  81 };
  82
  83 /* valid values for service curve flags */
  84 #define HFSCF_M1_PCT            0x1     /* m1 is in percentage */
  85 #define HFSCF_M2_PCT            0x10    /* m2 is in percentage */
  86
  87 #define HFSCF_USERFLAGS         (HFSCF_M1_PCT | HFSCF_M2_PCT)
  88
  89 /* special class handles */
  90 #define HFSC_NULLCLASS_HANDLE   0
  91 #define HFSC_MAX_CLASSES        64
  92
  93 /* hfsc class flags */
  94 #define HFCF_RED                0x0001  /* use RED */
  95 #define HFCF_ECN                0x0002  /* use ECN with RED/BLUE/SFB */
  96 #define HFCF_RIO                0x0004  /* use RIO */
  97 #define HFCF_CLEARDSCP          0x0010  /* clear diffserv codepoint */
  98 #define HFCF_BLUE               0x0100  /* use BLUE */
  99 #define HFCF_SFB                0x0200  /* use SFB */
 100 #define HFCF_FLOWCTL            0x0400  /* enable flow control advisories */
 101 #define HFCF_DEFAULTCLASS       0x1000  /* default class */
 102 #ifdef BSD_KERNEL_PRIVATE
 103 #define HFCF_RSC                0x10000 /* has realtime sc */
 104 #define HFCF_FSC                0x20000 /* has linkshare sc */
 105 #define HFCF_USC                0x40000 /* has upperlimit sc */
 106 #define HFCF_LAZY               0x10000000 /* on-demand resource allocation */
 107 #endif /* BSD_KERNEL_PRIVATE */
 108
 109 #define HFCF_USERFLAGS                                                  \
 110         (HFCF_RED | HFCF_ECN | HFCF_RIO | HFCF_CLEARDSCP | HFCF_BLUE |  \
 111         HFCF_SFB | HFCF_FLOWCTL | HFCF_DEFAULTCLASS)
 112
 113 #ifdef BSD_KERNEL_PRIVATE
 114 #define HFCF_BITS \
 115         "\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT" \
 116         "\21RSC\22FSC\23USC\35LAZY"
 117 #else
 118 #define HFCF_BITS \
 119         "\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT"
 120 #endif /* !BSD_KERNEL_PRIVATE */
 121
 122 /* service curve types */
 123 #define HFSC_REALTIMESC         1
 124 #define HFSC_LINKSHARINGSC      2
 125 #define HFSC_UPPERLIMITSC       4
 126 #define HFSC_DEFAULTSC          (HFSC_REALTIMESC|HFSC_LINKSHARINGSC)
 127
 128 struct hfsc_classstats {
 129         u_int32_t               class_id;
 130         u_int32_t               class_handle;
 131         struct service_curve    rsc;
 132         struct service_curve    fsc;
 133         struct service_curve    usc;    /* upper limit service curve */
 134
 135         u_int64_t               total;  /* total work in bytes */
 136         u_int64_t               cumul;  /* cumulative work in bytes */
 137                                         /*   done by real-time criteria */
 138         u_int64_t               d;              /* deadline */
 139         u_int64_t               e;              /* eligible time */
 140         u_int64_t               vt;             /* virtual time */
 141         u_int64_t               f;              /* fit time for upper-limit */
 142
 143         /* info helpful for debugging */
 144         u_int64_t               initvt;         /* init virtual time */
 145         u_int64_t               vtoff;          /* cl_vt_ipoff */
 146         u_int64_t               cvtmax;         /* cl_maxvt */
 147         u_int64_t               myf;            /* cl_myf */
 148         u_int64_t               cfmin;          /* cl_mincf */
 149         u_int64_t               cvtmin;         /* cl_mincvt */
 150         u_int64_t               myfadj;         /* cl_myfadj */
 151         u_int64_t               vtadj;          /* cl_vtadj */
 152         u_int64_t               cur_time;
 153         u_int32_t               machclk_freq;
 154
 155         u_int32_t               qlength;
 156         u_int32_t               qlimit;
 157         struct pktcntr          xmit_cnt;
 158         struct pktcntr          drop_cnt;
 159         u_int32_t               period;
 160
 161         u_int32_t               vtperiod;       /* vt period sequence no */
 162         u_int32_t               parentperiod;   /* parent's vt period seqno */
 163         int                     nactive;        /* number of active children */
 164
 165         /* RED, RIO, BLUE, SFB related info */
 166         classq_type_t           qtype;
 167         union {
 168                 /* RIO has 3 red stats */
 169                 struct red_stats        red[RIO_NDROPPREC];
 170                 struct blue_stats       blue;
 171                 struct sfb_stats        sfb;
 172         };
 173         classq_state_t          qstate;
 174 };
 175
 176 #ifdef BSD_KERNEL_PRIVATE
 177 #include <sys/queue.h>
 178 /*
 179  * kernel internal service curve representation
 180  *      coordinates are given by 64 bit unsigned integers.
 181  *      x-axis: unit is clock count.  for the intel x86 architecture,
 182  *              the raw Pentium TSC (Timestamp Counter) value is used.
 183  *              virtual time is also calculated in this time scale.
 184  *      y-axis: unit is byte.
 185  *
 186  *      the service curve parameters are converted to the internal
 187  *      representation.
 188  *      the slope values are scaled to avoid overflow.
 189  *      the inverse slope values as well as the y-projection of the 1st
 190  *      segment are kept in order to to avoid 64-bit divide operations
 191  *      that are expensive on 32-bit architectures.
 192  *
 193  *  note: Intel Pentium TSC never wraps around in several thousands of years.
 194  *      x-axis doesn't wrap around for 1089 years with 1GHz clock.
 195  *      y-axis doesn't wrap around for 4358 years with 1Gbps bandwidth.
 196  */
 197
 198 /* kernel internal representation of a service curve */
 199 struct internal_sc {
 200         u_int64_t       sm1;    /* scaled slope of the 1st segment */
 201         u_int64_t       ism1;   /* scaled inverse-slope of the 1st segment */
 202         u_int64_t       dx;     /* the x-projection of the 1st segment */
 203         u_int64_t       dy;     /* the y-projection of the 1st segment */
 204         u_int64_t       sm2;    /* scaled slope of the 2nd segment */
 205         u_int64_t       ism2;   /* scaled inverse-slope of the 2nd segment */
 206 };
 207
 208 /* runtime service curve */
 209 struct runtime_sc {
 210         u_int64_t       x;      /* current starting position on x-axis */
 211         u_int64_t       y;      /* current starting position on x-axis */
 212         u_int64_t       sm1;    /* scaled slope of the 1st segment */
 213         u_int64_t       ism1;   /* scaled inverse-slope of the 1st segment */
 214         u_int64_t       dx;     /* the x-projection of the 1st segment */
 215         u_int64_t       dy;     /* the y-projection of the 1st segment */
 216         u_int64_t       sm2;    /* scaled slope of the 2nd segment */
 217         u_int64_t       ism2;   /* scaled inverse-slope of the 2nd segment */
 218 };
 219
 220 /* for TAILQ based ellist and actlist implementation */
 221 struct hfsc_class;
 222 typedef TAILQ_HEAD(_eligible, hfsc_class) ellist_t;
 223 typedef TAILQ_ENTRY(hfsc_class) elentry_t;
 224 typedef TAILQ_HEAD(_active, hfsc_class) actlist_t;
 225 typedef TAILQ_ENTRY(hfsc_class) actentry_t;
 226 #define ellist_first(s)         TAILQ_FIRST(s)
 227 #define actlist_first(s)        TAILQ_FIRST(s)
 228 #define actlist_last(s)         TAILQ_LAST(s, _active)
 229
 230 struct hfsc_class {
 231         u_int32_t       cl_id;          /* class id (just for debug) */
 232         u_int32_t       cl_handle;      /* class handle */
 233         struct hfsc_if  *cl_hif;        /* back pointer to struct hfsc_if */
 234         u_int32_t       cl_flags;       /* misc flags */
 235
 236         struct hfsc_class *cl_parent;   /* parent class */
 237         struct hfsc_class *cl_siblings; /* sibling classes */
 238         struct hfsc_class *cl_children; /* child classes */
 239
 240         class_queue_t   cl_q;           /* class queue structure */
 241         u_int32_t       cl_qflags;      /* class queue flags */
 242         union {
 243                 void            *ptr;
 244                 struct red      *red;   /* RED state */
 245                 struct rio      *rio;   /* RIO state */
 246                 struct blue     *blue;  /* BLUE state */
 247                 struct sfb      *sfb;   /* SFB state */
 248         } cl_qalg;
 249
 250         u_int64_t       cl_total;       /* total work in bytes */
 251         u_int64_t       cl_cumul;       /* cumulative work in bytes */
 252                                         /*   done by real-time criteria */
 253         u_int64_t       cl_d;           /* deadline */
 254         u_int64_t       cl_e;           /* eligible time */
 255         u_int64_t       cl_vt;          /* virtual time */
 256         u_int64_t       cl_f;           /* time when this class will fit for */
 257                                         /*   link-sharing, max(myf, cfmin) */
 258         u_int64_t       cl_myf;         /* my fit-time (as calculated from */
 259                                         /*   this class's own upperlimit */
 260                                         /*   curve) */
 261         u_int64_t       cl_myfadj;      /* my fit-time adjustment */
 262                                         /*   (to cancel history dependence) */
 263         u_int64_t       cl_cfmin;       /* earliest children's fit-time (used */
 264                                         /*   with cl_myf to obtain cl_f) */
 265         u_int64_t       cl_cvtmin;      /* minimal virtual time among the */
 266                                         /*   children fit for link-sharing */
 267                                         /*   (monotonic within a period) */
 268         u_int64_t       cl_vtadj;       /* intra-period cumulative vt */
 269                                         /*   adjustment */
 270         u_int64_t       cl_vtoff;       /* inter-period cumulative vt offset */
 271         u_int64_t       cl_cvtmax;      /* max child's vt in the last period */
 272
 273         u_int64_t       cl_initvt;      /* init virtual time (for debugging) */
 274
 275         struct service_curve cl_rsc0;   /* external real-time service curve */
 276         struct service_curve cl_fsc0;   /* external fair service curve */
 277         struct service_curve cl_usc0;   /* external uppperlimit service curve */
 278         struct internal_sc cl_rsc;      /* internal real-time service curve */
 279         struct internal_sc cl_fsc;      /* internal fair service curve */
 280         struct internal_sc cl_usc;      /* internal upperlimit service curve */
 281         struct runtime_sc  cl_deadline; /* deadline curve */
 282         struct runtime_sc  cl_eligible; /* eligible curve */
 283         struct runtime_sc  cl_virtual;  /* virtual curve */
 284         struct runtime_sc  cl_ulimit;   /* upperlimit curve */
 285
 286         u_int32_t       cl_vtperiod;    /* vt period sequence no */
 287         u_int32_t       cl_parentperiod;  /* parent's vt period seqno */
 288         u_int32_t       cl_nactive;     /* number of active children */
 289         actlist_t       cl_actc;        /* active children list */
 290
 291         actentry_t      cl_actlist;     /* active children list entry */
 292         elentry_t       cl_ellist;      /* eligible list entry */
 293
 294         struct {
 295                 struct pktcntr  xmit_cnt;
 296                 struct pktcntr  drop_cnt;
 297                 u_int32_t period;
 298         } cl_stats;
 299 };
 300
 301 #define cl_red  cl_qalg.red
 302 #define cl_rio  cl_qalg.rio
 303 #define cl_blue cl_qalg.blue
 304 #define cl_sfb  cl_qalg.sfb
 305
 306 /* hfsc_if flags */
 307 #define HFSCIFF_ALTQ            0x1     /* configured via PF/ALTQ */
 308
 309 /*
 310  * hfsc interface state
 311  */
 312 struct hfsc_if {
 313         struct ifclassq         *hif_ifq;       /* backpointer to ifclassq */
 314         struct hfsc_class       *hif_rootclass;         /* root class */
 315         struct hfsc_class       *hif_defaultclass;      /* default class */
 316         struct hfsc_class       **hif_class_tbl;
 317         struct hfsc_class       *hif_pollcache; /* cache for poll operation */
 318
 319         u_int32_t               hif_flags;      /* flags */
 320         u_int32_t               hif_maxclasses; /* max # of classes in table */
 321         u_int32_t               hif_classes;    /* # of classes in the tree */
 322         u_int32_t               hif_packets;    /* # of packets in the tree */
 323         u_int32_t               hif_classid;    /* class id sequence number */
 324         u_int64_t               hif_eff_rate;   /* last known effective rate */
 325
 326         ellist_t hif_eligible;                  /* eligible list */
 327 };
 328
 329 #define HFSCIF_IFP(_hif)        ((_hif)->hif_ifq->ifcq_ifp)
 330
 331 extern void hfsc_init(void);
 332 extern struct hfsc_if *hfsc_alloc(struct ifnet *, int, boolean_t);
 333 extern int hfsc_destroy(struct hfsc_if *);
 334 extern void hfsc_purge(struct hfsc_if *);
 335 extern void hfsc_event(struct hfsc_if *, cqev_t);
 336 extern int hfsc_add_queue(struct hfsc_if *, struct service_curve *,
 337     struct service_curve *, struct service_curve *, u_int32_t, int,
 338     u_int32_t, u_int32_t, struct hfsc_class **);
 339 extern int hfsc_remove_queue(struct hfsc_if *, u_int32_t);
 340 extern int hfsc_get_class_stats(struct hfsc_if *, u_int32_t,
 341     struct hfsc_classstats *);
 342 extern int hfsc_enqueue(struct hfsc_if *, struct hfsc_class *,
 343     struct mbuf *, struct pf_mtag *);
 344 extern struct mbuf *hfsc_dequeue(struct hfsc_if *, cqdq_op_t);
 345 extern int hfsc_setup_ifclassq(struct ifclassq *, u_int32_t);
 346 extern int hfsc_teardown_ifclassq(struct ifclassq *);
 347 extern int hfsc_getqstats_ifclassq(struct ifclassq *, u_int32_t,
 348     struct if_ifclassq_stats *);
 349 #endif /* BSD_KERNEL_PRIVATE */
 350
 351 #ifdef __cplusplus
 352 }
 353 #endif
 354 #endif /* PRIVATE */
 355 #endif /* _NET_PKTSCHED_PKTSCHED_HFSC_H_ */