[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/altq/altq_jobs.c

Version: -  FREEBSD  -  FREEBSD10  -  FREEBSD9  -  FREEBSD92  -  FREEBSD91  -  FREEBSD90  -  FREEBSD8  -  FREEBSD82  -  FREEBSD81  -  FREEBSD80  -  FREEBSD7  -  FREEBSD74  -  FREEBSD73  -  FREEBSD72  -  FREEBSD71  -  FREEBSD70  -  FREEBSD6  -  FREEBSD64  -  FREEBSD63  -  FREEBSD62  -  FREEBSD61  -  FREEBSD60  -  FREEBSD5  -  FREEBSD55  -  FREEBSD54  -  FREEBSD53  -  FREEBSD52  -  FREEBSD51  -  FREEBSD50  -  FREEBSD4  -  FREEBSD3  -  FREEBSD22  -  cheribsd  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1  -  FREEBSD-LIBC  -  FREEBSD8-LIBC  -  FREEBSD7-LIBC  -  FREEBSD6-LIBC  -  GLIBC27 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: altq_jobs.c,v 1.6 2010/04/09 19:32:45 plunky Exp $     */
    2 /*      $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */
    3 /*
    4  * Copyright (c) 2001, the Rector and Board of Visitors of the
    5  * University of Virginia.
    6  * All rights reserved.
    7  *
    8  * Redistribution and use in source and binary forms,
    9  * with or without modification, are permitted provided
   10  * that the following conditions are met:
   11  *
   12  * Redistributions of source code must retain the above
   13  * copyright notice, this list of conditions and the following
   14  * disclaimer.
   15  *
   16  * Redistributions in binary form must reproduce the above
   17  * copyright notice, this list of conditions and the following
   18  * disclaimer in the documentation and/or other materials provided
   19  * with the distribution.
   20  *
   21  * Neither the name of the University of Virginia nor the names
   22  * of its contributors may be used to endorse or promote products
   23  * derived from this software without specific prior written
   24  * permission.
   25  *
   26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
   27  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
   28  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
   29  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   30  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
   31  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
   32  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   33  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   34  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   35  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
   37  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
   38  * THE POSSIBILITY OF SUCH DAMAGE.
   39  */
   40 /*                                                                     
   41  * JoBS - altq prototype implementation                                
   42  *                                                                     
   43  * Author: Nicolas Christin <nicolas@cs.virginia.edu>
   44  *
   45  * JoBS algorithms originally devised and proposed by                  
   46  * Nicolas Christin and Jorg Liebeherr.
   47  * Grateful acknowledgments to Tarek Abdelzaher for his help and       
   48  * comments, and to Kenjiro Cho for some helpful advice.
   49  * Contributed by the Multimedia Networks Group at the University
   50  * of Virginia. 
   51  *
   52  * Papers and additional info can be found at 
   53  * http://qosbox.cs.virginia.edu
   54  *                                                                      
   55  */                                                                    
   56 
   57 /*
   58  * JoBS queue
   59  */
   60 
   61 #include <sys/cdefs.h>
   62 __KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.6 2010/04/09 19:32:45 plunky Exp $");
   63 
   64 #ifdef _KERNEL_OPT
   65 #include "opt_altq.h"
   66 #include "opt_inet.h"
   67 #endif
   68 
   69 #ifdef ALTQ_JOBS  /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */
   70 
   71 #include <sys/param.h>
   72 #include <sys/malloc.h>
   73 #include <sys/mbuf.h>
   74 #include <sys/socket.h>
   75 #include <sys/sockio.h>
   76 #include <sys/systm.h>
   77 #include <sys/proc.h>
   78 #include <sys/errno.h>
   79 #include <sys/kernel.h>
   80 #include <sys/queue.h>
   81 #include <sys/kauth.h>
   82 
   83 #ifdef __FreeBSD__
   84 #include <sys/limits.h>
   85 #endif
   86 
   87 #include <net/if.h>
   88 #include <net/if_types.h>
   89 
   90 #include <altq/altq.h>
   91 #include <altq/altq_conf.h>
   92 #include <altq/altq_jobs.h>
   93 
   94 #ifdef ALTQ3_COMPAT
   95 /*
   96  * function prototypes
   97  */
   98 static struct jobs_if *jobs_attach(struct ifaltq *, u_int, u_int, u_int);
   99 static int jobs_detach(struct jobs_if *);
  100 static int jobs_clear_interface(struct jobs_if *);
  101 static int jobs_request(struct ifaltq *, int, void *);
  102 static void jobs_purge(struct jobs_if *);
  103 static struct jobs_class *jobs_class_create(struct jobs_if *,
  104     int, int64_t, int64_t, int64_t, int64_t, int64_t, int);
  105 static int jobs_class_destroy(struct jobs_class *);
  106 static int jobs_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
  107 static struct mbuf *jobs_dequeue(struct ifaltq *, int);
  108 
  109 static int jobs_addq(struct jobs_class *, struct mbuf *, struct jobs_if*);
  110 static struct mbuf *jobs_getq(struct jobs_class *);
  111 static struct mbuf *jobs_pollq(struct jobs_class *);
  112 static void jobs_purgeq(struct jobs_class *);
  113 
  114 static int jobscmd_if_attach(struct jobs_attach *);
  115 static int jobscmd_if_detach(struct jobs_interface *);
  116 static int jobscmd_add_class(struct jobs_add_class *);
  117 static int jobscmd_delete_class(struct jobs_delete_class *);
  118 static int jobscmd_modify_class(struct jobs_modify_class *);
  119 static int jobscmd_add_filter(struct jobs_add_filter *);
  120 static int jobscmd_delete_filter(struct jobs_delete_filter *);
  121 static int jobscmd_class_stats(struct jobs_class_stats *);
  122 static void get_class_stats(struct class_stats *, struct jobs_class *);
  123 static struct jobs_class *clh_to_clp(struct jobs_if *, u_long);
  124 static u_long clp_to_clh(struct jobs_class *);
  125 
  126 static TSLIST *tslist_alloc(void);
  127 static void tslist_destroy(struct jobs_class *);
  128 static int tslist_enqueue(struct jobs_class *, u_int64_t);
  129 static void tslist_dequeue(struct jobs_class *);
  130 static void tslist_drop(struct jobs_class *);
  131 
  132 static int enforce_wc(struct jobs_if *);
  133 static int64_t* adjust_rates_rdc(struct jobs_if *);
  134 static int64_t* assign_rate_drops_adc(struct jobs_if *);
  135 static int64_t* update_error(struct jobs_if *);
  136 static int min_rates_adc(struct jobs_if *);
  137 static int64_t proj_delay(struct jobs_if *, int);
  138 static int pick_dropped_rlc(struct jobs_if *);
  139 
  140 altqdev_decl(jobs);
  141 
  142 /* jif_list keeps all jobs_if's allocated. */
  143 static struct jobs_if *jif_list = NULL;
  144 
  145 typedef unsigned long long ull;
  146 
  147 /* setup functions */
  148 
  149 static struct jobs_if *
  150 jobs_attach(struct ifaltq *ifq, u_int bandwidth, u_int qlimit, u_int separate)
  151 {
  152         struct jobs_if *jif;
  153 
  154         jif = malloc(sizeof(struct jobs_if), M_DEVBUF, M_WAITOK|M_ZERO);
  155         if (jif == NULL)
  156                 return (NULL);
  157 
  158         jif->jif_bandwidth = bandwidth;
  159         jif->jif_qlimit = qlimit;
  160         jif->jif_separate = separate;
  161 #ifdef ALTQ_DEBUG
  162         printf("JoBS bandwidth = %d bps\n", (int)bandwidth);
  163         printf("JoBS buffer size = %d pkts [%s]\n",
  164                (int)qlimit, separate?"separate buffers":"shared buffer");
  165 #endif
  166         jif->jif_maxpri = -1;
  167         jif->jif_ifq = ifq;
  168 
  169         jif->wc_cycles_enqueue = 0;
  170         jif->avg_cycles_enqueue = 0;
  171         jif->avg_cycles2_enqueue = 0;
  172         jif->bc_cycles_enqueue = ALTQ_INFINITY;
  173         jif->wc_cycles_dequeue = 0;
  174         jif->avg_cycles_dequeue = 0;
  175         jif->avg_cycles2_dequeue = 0;
  176         jif->bc_cycles_dequeue = ALTQ_INFINITY;
  177         jif->total_enqueued = 0;
  178         jif->total_dequeued = 0;
  179 
  180         /* add this state to the jobs list */
  181         jif->jif_next = jif_list;
  182         jif_list = jif;
  183 
  184         return (jif);
  185 }
  186 
  187 static int
  188 jobs_detach(struct jobs_if *jif)
  189 {
  190         (void)jobs_clear_interface(jif);
  191 
  192         /* remove this interface from the jif list */
  193         if (jif_list == jif)
  194                 jif_list = jif->jif_next;
  195         else {
  196                 struct jobs_if *p;
  197 
  198                 for (p = jif_list; p != NULL; p = p->jif_next)
  199                         if (p->jif_next == jif) {
  200                                 p->jif_next = jif->jif_next;
  201                                 break;
  202                         }
  203                 ASSERT(p != NULL);
  204         }
  205         free(jif, M_DEVBUF);
  206         return (0);
  207 }
  208 
  209 /*
  210  * bring the interface back to the initial state by discarding
  211  * all the filters and classes.
  212  */
  213 static int
  214 jobs_clear_interface(struct jobs_if *jif)
  215 {
  216         struct jobs_class       *cl;
  217         int     pri;
  218 
  219         /* free the filters for this interface */
  220         acc_discard_filters(&jif->jif_classifier, NULL, 1);
  221 
  222         /* clear out the classes */
  223         for (pri = 0; pri <= jif->jif_maxpri; pri++)
  224                 if ((cl = jif->jif_classes[pri]) != NULL)
  225                         jobs_class_destroy(cl);
  226 
  227         return (0);
  228 }
  229 
  230 static int
  231 jobs_request(struct ifaltq *ifq, int req, void *arg)
  232 {
  233         struct jobs_if  *jif = (struct jobs_if *)ifq->altq_disc;
  234 
  235         switch (req) {
  236         case ALTRQ_PURGE:
  237                 jobs_purge(jif);
  238                 break;
  239         }
  240         return (0);
  241 }
  242 
  243 /* discard all the queued packets on the interface */
  244 static void
  245 jobs_purge(struct jobs_if *jif)
  246 {
  247         struct jobs_class *cl;
  248         int pri;
  249 
  250         for (pri = 0; pri <= jif->jif_maxpri; pri++) {
  251                 if ((cl = jif->jif_classes[pri]) != NULL && !qempty(cl->cl_q))
  252                         jobs_purgeq(cl);
  253         }
  254         if (ALTQ_IS_ENABLED(jif->jif_ifq))
  255                 jif->jif_ifq->ifq_len = 0;
  256 }
  257 
  258 static struct jobs_class *
  259 jobs_class_create(struct jobs_if *jif, int pri, int64_t adc, int64_t rdc,
  260     int64_t alc, int64_t rlc, int64_t arc, int flags)
  261 {
  262         struct jobs_class *cl, *scan1, *scan2;
  263         int s;
  264         int class_exists1, class_exists2;
  265         int i, j;
  266         int64_t tmp[JOBS_MAXPRI];
  267         u_int64_t now;
  268 
  269         if ((cl = jif->jif_classes[pri]) != NULL) {
  270                 /* modify the class instead of creating a new one */
  271                 s = splnet();
  272                 if (!qempty(cl->cl_q))
  273                         jobs_purgeq(cl);
  274                 splx(s);
  275         } else {
  276                 cl = malloc(sizeof(struct jobs_class), M_DEVBUF,
  277                     M_WAITOK|M_ZERO);
  278                 if (cl == NULL)
  279                         return (NULL);
  280 
  281                 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF,
  282                     M_WAITOK|M_ZERO);
  283                 if (cl->cl_q == NULL)
  284                         goto err_ret;
  285 
  286                 cl->arv_tm = tslist_alloc();
  287                 if (cl->arv_tm == NULL)
  288                         goto err_ret;
  289         }
  290 
  291         jif->jif_classes[pri] = cl;
  292 
  293         if (flags & JOCF_DEFAULTCLASS)
  294                 jif->jif_default = cl;
  295 
  296         qtype(cl->cl_q) = Q_DROPTAIL;
  297         qlen(cl->cl_q) = 0;
  298         cl->service_rate = 0;
  299         cl->min_rate_adc = 0;
  300         cl->current_loss = 0;
  301         cl->cl_period = 0;
  302         PKTCNTR_RESET(&cl->cl_arrival);
  303         PKTCNTR_RESET(&cl->cl_rin);
  304         PKTCNTR_RESET(&cl->cl_rout);
  305         PKTCNTR_RESET(&cl->cl_rout_th);
  306         PKTCNTR_RESET(&cl->cl_dropcnt);
  307         PKTCNTR_RESET(&cl->st_arrival);
  308         PKTCNTR_RESET(&cl->st_rin);
  309         PKTCNTR_RESET(&cl->st_rout);
  310         PKTCNTR_RESET(&cl->st_dropcnt);
  311         cl->st_service_rate = 0;
  312         cl->cl_lastdel = 0;
  313         cl->cl_avgdel = 0;
  314         cl->adc_violations = 0;
  315 
  316         if (adc == -1) {
  317                 cl->concerned_adc = 0;
  318                 adc = ALTQ_INFINITY;
  319         } else 
  320                 cl->concerned_adc = 1;
  321 
  322         if (alc == -1) {
  323                 cl->concerned_alc = 0;
  324                 alc = ALTQ_INFINITY;
  325         } else 
  326                 cl->concerned_alc = 1;
  327 
  328         if (rdc == -1) {
  329                 rdc = 0;
  330                 cl->concerned_rdc = 0;
  331         } else 
  332                 cl->concerned_rdc = 1;
  333 
  334         if (rlc == -1) {
  335                 rlc = 0;
  336                 cl->concerned_rlc = 0;
  337         } else 
  338                 cl->concerned_rlc = 1;
  339 
  340         if (arc == -1) {
  341                 arc = 0;
  342                 cl->concerned_arc = 0;
  343         } else
  344                 cl->concerned_arc = 1;
  345 
  346         cl->cl_rdc=rdc;
  347 
  348         if (cl->concerned_adc) {
  349                 /* adc is given in us, convert it to clock ticks */
  350                 cl->cl_adc = (u_int64_t)(adc*machclk_freq/GRANULARITY);
  351         } else
  352                 cl->cl_adc = adc;
  353 
  354         if (cl->concerned_arc) {
  355                 /* arc is given in bps, convert it to internal unit */
  356                 cl->cl_arc = (u_int64_t)(bps_to_internal(arc));
  357         } else
  358                 cl->cl_arc = arc;
  359 
  360         cl->cl_rlc=rlc;
  361         cl->cl_alc=alc;
  362         cl->delay_prod_others = 0;
  363         cl->loss_prod_others = 0;
  364         cl->cl_flags = flags;
  365         cl->cl_pri = pri;
  366         if (pri > jif->jif_maxpri)
  367                 jif->jif_maxpri = pri;
  368         cl->cl_jif = jif;
  369         cl->cl_handle = (u_long)cl;  /* just a pointer to this class */
  370 
  371         /*
  372          * update delay_prod_others and loss_prod_others
  373          * in all classes if needed
  374          */
  375 
  376         if (cl->concerned_rdc) {
  377                 for (i = 0; i <= jif->jif_maxpri; i++) {
  378                         scan1 = jif->jif_classes[i];
  379                         class_exists1 = (scan1 != NULL);
  380                         if (class_exists1) {
  381                                 tmp[i] = 1;
  382                                 for (j = 0; j <= i-1; j++) {
  383                                         scan2 = jif->jif_classes[j];
  384                                         class_exists2 = (scan2 != NULL);
  385                                         if (class_exists2
  386                                             && scan2->concerned_rdc)
  387                                                 tmp[i] *= scan2->cl_rdc;
  388                                 }
  389                         } else
  390                                 tmp[i] = 0;
  391                 }
  392 
  393                 for (i = 0; i <= jif->jif_maxpri; i++) {
  394                         scan1 = jif->jif_classes[i];
  395                         class_exists1 = (scan1 != NULL);
  396                         if (class_exists1) {
  397                                 scan1->delay_prod_others = 1;
  398                                 for (j = 0; j <= jif->jif_maxpri; j++) {
  399                                         scan2 = jif->jif_classes[j];
  400                                         class_exists2 = (scan2 != NULL);
  401                                         if (class_exists2 && j != i
  402                                             && scan2->concerned_rdc)
  403                                                 scan1->delay_prod_others *= tmp[j];
  404                                 }
  405                         }
  406                 }
  407         }
  408 
  409         if (cl->concerned_rlc) {
  410                 for (i = 0; i <= jif->jif_maxpri; i++) {
  411                         scan1 = jif->jif_classes[i];
  412                         class_exists1 = (scan1 != NULL);
  413                         if (class_exists1) {
  414                                 tmp[i] = 1;
  415                                 for (j = 0; j <= i-1; j++) {
  416                                         scan2 = jif->jif_classes[j];
  417                                         class_exists2 = (scan2 != NULL);
  418                                         if (class_exists2
  419                                             && scan2->concerned_rlc)
  420                                                 tmp[i] *= scan2->cl_rlc;
  421                                 }
  422                         } else
  423                                 tmp[i] = 0;
  424                 }
  425 
  426                 for (i = 0; i <= jif->jif_maxpri; i++) {
  427                         scan1 = jif->jif_classes[i];
  428                         class_exists1 = (scan1 != NULL);
  429                         if (class_exists1) {
  430                                 scan1->loss_prod_others = 1;
  431                                 for (j = 0; j <= jif->jif_maxpri; j++) {
  432                                         scan2 = jif->jif_classes[j];
  433                                         class_exists2 = (scan2 != NULL);
  434                                         if (class_exists2 && j != i
  435                                             && scan2->concerned_rlc)
  436                                                 scan1->loss_prod_others *= tmp[j];
  437                                 }
  438                         }
  439                 }
  440         }
  441 
  442         now = read_machclk();
  443         cl->idletime = now;
  444         return (cl);
  445 
  446  err_ret:
  447         if (cl->cl_q != NULL)
  448                 free(cl->cl_q, M_DEVBUF);
  449         if (cl->arv_tm != NULL)
  450                 free(cl->arv_tm, M_DEVBUF);
  451 
  452         free(cl, M_DEVBUF);
  453         return (NULL);
  454 }
  455 
  456 static int
  457 jobs_class_destroy(struct jobs_class *cl)
  458 {
  459         struct jobs_if *jif;
  460         int s, pri;
  461 
  462         s = splnet();
  463 
  464         /* delete filters referencing to this class */
  465         acc_discard_filters(&cl->cl_jif->jif_classifier, cl, 0);
  466 
  467         if (!qempty(cl->cl_q))
  468                 jobs_purgeq(cl);
  469 
  470         jif = cl->cl_jif;
  471         jif->jif_classes[cl->cl_pri] = NULL;
  472         if (jif->jif_maxpri == cl->cl_pri) {
  473                 for (pri = cl->cl_pri; pri >= 0; pri--)
  474                         if (jif->jif_classes[pri] != NULL) {
  475                                 jif->jif_maxpri = pri;
  476                                 break;
  477                         }
  478                 if (pri < 0)
  479                         jif->jif_maxpri = -1;
  480         }
  481         splx(s);
  482 
  483         tslist_destroy(cl);
  484         free(cl->cl_q, M_DEVBUF);
  485         free(cl, M_DEVBUF);
  486         return (0);
  487 }
  488 
  489 /*
  490  * jobs_enqueue is an enqueue function to be registered to
  491  * (*altq_enqueue) in struct ifaltq.
  492  */
  493 static int
  494 jobs_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr)
  495 {
  496         struct jobs_if  *jif = (struct jobs_if *)ifq->altq_disc;
  497         struct jobs_class *cl, *scan;
  498         int len;
  499         int return_flag;
  500         int pri;
  501         u_int64_t now;
  502         u_int64_t old_arv;
  503         int64_t* delta_rate;
  504         u_int64_t tstamp1, tstamp2, cycles; /* used for benchmarking only */
  505 
  506         jif->total_enqueued++;
  507         now = read_machclk();
  508         tstamp1 = now;
  509 
  510         return_flag = 0;
  511 
  512         /* proceed with packet enqueuing */
  513 
  514         if (IFQ_IS_EMPTY(ifq)) {
  515                 for (pri=0; pri <= jif->jif_maxpri; pri++) {
  516                         scan = jif->jif_classes[pri];
  517                         if (scan != NULL) {
  518                                 /*
  519                                  * reset all quantities, except:
  520                                  * average delay, number of violations
  521                                  */
  522                                 PKTCNTR_RESET(&scan->cl_rin);
  523                                 PKTCNTR_RESET(&scan->cl_rout);
  524                                 PKTCNTR_RESET(&scan->cl_rout_th);
  525                                 PKTCNTR_RESET(&scan->cl_arrival);
  526                                 PKTCNTR_RESET(&scan->cl_dropcnt);       
  527                                 scan->cl_lastdel = 0;
  528                                 scan->current_loss = 0;
  529                                 scan->service_rate = 0;
  530                                 scan->idletime = now;
  531                                 scan->cl_last_rate_update = now;
  532                         }
  533                 }
  534         }
  535 
  536         /* grab class set by classifier */
  537         if (pktattr == NULL || (cl = pktattr->pattr_class) == NULL)
  538                 cl = jif->jif_default;
  539 
  540         len = m_pktlen(m);
  541         old_arv = cl->cl_arrival.bytes;
  542         PKTCNTR_ADD(&cl->cl_arrival, (int)len);
  543         PKTCNTR_ADD(&cl->cl_rin, (int)len);
  544         PKTCNTR_ADD(&cl->st_arrival, (int)len);
  545         PKTCNTR_ADD(&cl->st_rin, (int)len);
  546 
  547         if (cl->cl_arrival.bytes < old_arv) {
  548                 /* deals w/ overflow */
  549                 for (pri=0; pri <= jif->jif_maxpri; pri++) {
  550                         scan = jif->jif_classes[pri];
  551                         if (scan != NULL) {
  552                                 /*
  553                                  * reset all quantities, except:
  554                                  * average delay, number of violations
  555                                  */
  556                                 PKTCNTR_RESET(&scan->cl_rin);
  557                                 PKTCNTR_RESET(&scan->cl_rout);
  558                                 PKTCNTR_RESET(&scan->cl_rout_th);
  559                                 PKTCNTR_RESET(&scan->cl_arrival);
  560                                 PKTCNTR_RESET(&scan->cl_dropcnt);       
  561                                 scan->current_loss = 0;
  562                                 scan->service_rate = 0;
  563                                 scan->idletime = now;
  564                                 scan->cl_last_rate_update = now;
  565                         }
  566                 }
  567                 PKTCNTR_ADD(&cl->cl_arrival, (int)len);
  568                 PKTCNTR_ADD(&cl->cl_rin, (int)len);
  569         }
  570 
  571         if (cl->cl_arrival.bytes > cl->cl_rin.bytes)
  572                 cl->current_loss =
  573                     ((cl->cl_arrival.bytes - cl->cl_rin.bytes) << SCALE_LOSS)
  574                     / cl->cl_arrival.bytes;
  575         else
  576                 cl->current_loss = 0;
  577 
  578         /* for MDRR: update theoretical value of the output curve */
  579 
  580         for (pri=0; pri <= jif->jif_maxpri; pri++) {
  581                 scan = jif->jif_classes[pri];
  582                 if (scan != NULL) {
  583                         if (scan->cl_last_rate_update == scan->idletime
  584                             || scan->cl_last_rate_update == 0)
  585                                 scan->cl_last_rate_update = now; /* initial case */
  586                         else
  587                                 scan->cl_rout_th.bytes +=
  588                                     delay_diff(now, scan->cl_last_rate_update)
  589                                     * scan->service_rate;
  590 
  591                         /*
  592                          * we don't really care about packets here
  593                          * WARNING: rout_th is SCALED
  594                          * (b/c of the service rate)
  595                          * for precision, as opposed to rout.
  596                          */
  597 
  598                         scan->cl_last_rate_update = now;
  599                 }
  600         }
  601 
  602         if (jobs_addq(cl, m, jif) != 0)
  603                 return_flag = ENOBUFS; /* signals there's a buffer overflow */
  604         else
  605                 IFQ_INC_LEN(ifq);
  606 
  607         /* successfully queued. */
  608 
  609         enforce_wc(jif);
  610 
  611         if (!min_rates_adc(jif)) {
  612                 delta_rate = assign_rate_drops_adc(jif);
  613                 if (delta_rate != NULL) {
  614                         for (pri = 0; pri <= jif->jif_maxpri; pri++)
  615                           if ((cl = jif->jif_classes[pri]) != NULL &&
  616                               !qempty(cl->cl_q))
  617                                 cl->service_rate += delta_rate[pri];
  618                         free(delta_rate, M_DEVBUF);
  619                 }
  620         }
  621 
  622         delta_rate = adjust_rates_rdc(jif);
  623 
  624         if (delta_rate != NULL) {
  625                 for (pri = 0; pri <= jif->jif_maxpri; pri++)
  626                         if ((cl = jif->jif_classes[pri]) != NULL &&
  627                             !qempty(cl->cl_q))
  628                                 cl->service_rate += delta_rate[pri];
  629                 free(delta_rate, M_DEVBUF);
  630         }
  631 
  632         tstamp2 = read_machclk();
  633         cycles = delay_diff(tstamp2, tstamp1);
  634         if (cycles > jif->wc_cycles_enqueue)
  635                 jif->wc_cycles_enqueue=cycles;
  636         if (cycles < jif->bc_cycles_enqueue)
  637                 jif->bc_cycles_enqueue=cycles;
  638 
  639         jif->avg_cycles_enqueue += cycles;
  640         jif->avg_cycles2_enqueue += cycles * cycles;
  641 
  642         return (return_flag);
  643 }
  644 
  645 /*
  646  * jobs_dequeue is a dequeue function to be registered to
  647  * (*altq_dequeue) in struct ifaltq.
  648  *
  649  * note: ALTDQ_POLL returns the next packet without removing the packet
  650  *      from the queue.  ALTDQ_REMOVE is a normal dequeue operation.
  651  *      ALTDQ_REMOVE must return the same packet if called immediately
  652  *      after ALTDQ_POLL.
  653  */
  654 
  655 static struct mbuf *
  656 jobs_dequeue(struct ifaltq *ifq, int op)
  657 {
  658         struct jobs_if  *jif = (struct jobs_if *)ifq->altq_disc;
  659         struct jobs_class *cl;
  660         struct mbuf *m;
  661         int pri;
  662         int svc_class;
  663         int64_t max_error;
  664         int64_t error;
  665         u_int64_t now;
  666         u_int64_t tstamp1, tstamp2, cycles;
  667 
  668         jif->total_dequeued++;
  669 
  670         now = read_machclk();
  671         tstamp1 = now;
  672 
  673         if (IFQ_IS_EMPTY(ifq)) {
  674                 /* no packet in the queue */
  675                 for (pri=0; pri <= jif->jif_maxpri; pri++) {
  676                   cl = jif->jif_classes[pri];
  677                   if (cl != NULL)
  678                     cl->idletime = now;
  679                 }
  680 
  681                 tstamp2 = read_machclk();
  682                 cycles = delay_diff(tstamp2, tstamp1);
  683                 if (cycles > jif->wc_cycles_dequeue)
  684                         jif->wc_cycles_dequeue = cycles;
  685                 if (cycles < jif->bc_cycles_dequeue)
  686                         jif->bc_cycles_dequeue = cycles;
  687 
  688                 jif->avg_cycles_dequeue += cycles;
  689                 jif->avg_cycles2_dequeue += cycles * cycles;
  690 
  691                 return (NULL);
  692         }
  693 
  694         /*
  695          * select the class whose actual tranmissions are the furthest
  696          * from the promised transmissions
  697          */
  698 
  699         max_error = -1;
  700         svc_class = -1;
  701 
  702         for (pri=0; pri <= jif->jif_maxpri; pri++) {
  703                 if (((cl = jif->jif_classes[pri]) != NULL)
  704                     && !qempty(cl->cl_q)) {
  705                         error = (int64_t)cl->cl_rout_th.bytes
  706                             -(int64_t)scale_rate(cl->cl_rout.bytes);
  707                         if (max_error == -1) {
  708                                 max_error = error;
  709                                 svc_class = pri;
  710                         } else if (error > max_error) {
  711                                 max_error = error;
  712                                 svc_class = pri;
  713                         }
  714                 }
  715         }
  716 
  717         if (svc_class != -1)
  718                 cl = jif->jif_classes[svc_class];
  719         else
  720                 cl = NULL;
  721 
  722         if (op == ALTDQ_POLL) {
  723                 tstamp2 = read_machclk();
  724                 cycles = delay_diff(tstamp2, tstamp1);
  725                 if (cycles > jif->wc_cycles_dequeue)
  726                         jif->wc_cycles_dequeue = cycles;
  727                 if (cycles < jif->bc_cycles_dequeue)
  728                         jif->bc_cycles_dequeue = cycles;
  729 
  730                 jif->avg_cycles_dequeue += cycles;
  731                 jif->avg_cycles2_dequeue += cycles * cycles;
  732 
  733                 return (jobs_pollq(cl));
  734         }
  735 
  736         if (cl != NULL)
  737                 m = jobs_getq(cl);
  738         else
  739                 m = NULL;
  740 
  741         if (m != NULL) {
  742                 IFQ_DEC_LEN(ifq);
  743                 if (qempty(cl->cl_q))
  744                         cl->cl_period++;
  745 
  746                 cl->cl_lastdel = (u_int64_t)delay_diff(now,
  747                     tslist_first(cl->arv_tm)->timestamp);
  748                 if (cl->concerned_adc
  749                     && (int64_t)cl->cl_lastdel > cl->cl_adc)
  750                         cl->adc_violations++;
  751                 cl->cl_avgdel  += ticks_to_secs(GRANULARITY*cl->cl_lastdel);
  752 
  753                 PKTCNTR_ADD(&cl->cl_rout, m_pktlen(m));
  754                 PKTCNTR_ADD(&cl->st_rout, m_pktlen(m));
  755         }
  756         if (cl != NULL)
  757                 tslist_dequeue(cl);             /* dequeue the timestamp */
  758 
  759         tstamp2 = read_machclk();
  760         cycles = delay_diff(tstamp2, tstamp1);
  761         if (cycles > jif->wc_cycles_dequeue)
  762                 jif->wc_cycles_dequeue = cycles;
  763         if (cycles < jif->bc_cycles_dequeue)
  764                 jif->bc_cycles_dequeue = cycles;
  765 
  766         jif->avg_cycles_dequeue += cycles;
  767         jif->avg_cycles2_dequeue += cycles * cycles;
  768 
  769         return (m);
  770 }
  771 
  772 static int
  773 jobs_addq(struct jobs_class *cl, struct mbuf *m, struct jobs_if *jif)
  774 {
  775         int victim;
  776         u_int64_t len;
  777         u_int64_t now;
  778         struct jobs_class* victim_class;
  779 
  780         victim = -1;
  781         victim_class = NULL;
  782         len = 0;
  783 
  784         now = read_machclk();
  785 
  786         if (jif->jif_separate && qlen(cl->cl_q) >= jif->jif_qlimit) {
  787                 /*
  788                  * separate buffers: no guarantees on packet drops
  789                  * can be offered
  790                  * thus we drop the incoming packet
  791                  */
  792                 len = (u_int64_t)m_pktlen(m);
  793                 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
  794                 PKTCNTR_SUB(&cl->cl_rin, (int)len);
  795                 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
  796                 PKTCNTR_SUB(&cl->st_rin, (int)len);
  797                 cl->current_loss += (len << SCALE_LOSS)
  798                     /cl->cl_arrival.bytes;
  799                 m_freem(m);
  800                 return (-1);
  801 
  802         } else if (!jif->jif_separate
  803                    && jif->jif_ifq->ifq_len >= jif->jif_qlimit) {
  804                 /* shared buffer: supports guarantees on losses */
  805                 if (!cl->concerned_rlc) {
  806                         if (!cl->concerned_alc) {
  807                                 /*
  808                                  * no ALC, no RLC on this class:
  809                                  * drop the incoming packet
  810                                  */
  811                                 len = (u_int64_t)m_pktlen(m);
  812                                 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
  813                                 PKTCNTR_SUB(&cl->cl_rin, (int)len);
  814                                 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
  815                                 PKTCNTR_SUB(&cl->st_rin, (int)len);
  816                                 cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
  817                                 m_freem(m);
  818                                 return (-1);
  819                         } else {
  820                                 /*
  821                                  * no RLC, but an ALC:
  822                                  * drop the incoming packet if possible
  823                                  */
  824                                 len = (u_int64_t)m_pktlen(m);
  825                                 if (cl->current_loss + (len << SCALE_LOSS)
  826                                     / cl->cl_arrival.bytes <= cl->cl_alc) {
  827                                         PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
  828                                         PKTCNTR_SUB(&cl->cl_rin, (int)len);
  829                                         PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
  830                                         PKTCNTR_SUB(&cl->st_rin, (int)len);
  831                                         cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
  832                                         m_freem(m);
  833                                         return (-1);
  834                                 } else {
  835                                         /*
  836                                          * the ALC would be violated:
  837                                          * pick another class
  838                                          */
  839                                         _addq(cl->cl_q, m);
  840                                         tslist_enqueue(cl, now);
  841 
  842                                         victim = pick_dropped_rlc(jif);
  843 
  844                                         if (victim == -1) {
  845                                                 /*
  846                                                  * something went wrong
  847                                                  * let us discard
  848                                                  * the incoming packet,
  849                                                  * regardless of what
  850                                                  * may happen...
  851                                                  */
  852                                                 victim_class = cl;
  853                                         } else
  854                                                 victim_class = jif->jif_classes[victim];
  855 
  856                                         if (victim_class != NULL) {
  857                                                 /*
  858                                                  * test for safety
  859                                                  * purposes...
  860                                                  * it must be true
  861                                                  */
  862                                                 m = _getq_tail(victim_class->cl_q);
  863                                                 len = (u_int64_t)m_pktlen(m);
  864                                                 PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
  865                                                 PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
  866                                                 PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
  867                                                 PKTCNTR_SUB(&victim_class->st_rin, (int)len);
  868                                                 victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
  869                                                 m_freem(m); /* the packet is trashed here */
  870                                                 tslist_drop(victim_class); /* and its timestamp as well */
  871                                         }
  872                                         return (-1);
  873                                 }
  874                         }
  875                 } else {
  876                         /*
  877                          * RLC on that class:
  878                          * pick class according to RLCs
  879                          */
  880                         _addq(cl->cl_q, m);
  881                         tslist_enqueue(cl, now);
  882 
  883                         victim = pick_dropped_rlc(jif);
  884                         if (victim == -1) {
  885                                 /*
  886                                  * something went wrong
  887                                  * let us discard the incoming packet,
  888                                  * regardless of what may happen...
  889                                  */
  890                                 victim_class = cl;
  891                         } else
  892                                 victim_class = jif->jif_classes[victim];
  893 
  894                         if (victim_class != NULL) {
  895                                 /*
  896                                  * test for safety purposes...
  897                                  * it must be true
  898                                  */
  899                                 m = _getq_tail(victim_class->cl_q);
  900                                 len = (u_int64_t)m_pktlen(m);
  901                                 PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
  902                                 PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
  903                                 PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
  904                                 PKTCNTR_SUB(&victim_class->st_rin, (int)len);
  905                                 victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
  906                                 m_freem(m); /* the packet is trashed here */
  907                                 tslist_drop(victim_class); /* and its timestamp as well */
  908                         }
  909                         return (-1);
  910                 }
  911         }
  912         /* else: no drop */
  913 
  914         _addq(cl->cl_q, m);
  915         tslist_enqueue(cl, now);
  916 
  917         return (0);
  918 }
  919 
  920 static struct mbuf *
  921 jobs_getq(struct jobs_class *cl)
  922 {
  923         return _getq(cl->cl_q);
  924 }
  925 
  926 static struct mbuf *
  927 jobs_pollq(struct jobs_class *cl)
  928 {
  929         return qhead(cl->cl_q);
  930 }
  931 
  932 static void
  933 jobs_purgeq(struct jobs_class *cl)
  934 {
  935         struct mbuf *m;
  936 
  937         if (qempty(cl->cl_q))
  938                 return;
  939 
  940         while ((m = _getq(cl->cl_q)) != NULL) {
  941                 PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m));
  942                 PKTCNTR_ADD(&cl->st_dropcnt, m_pktlen(m));
  943                 m_freem(m);
  944                 tslist_drop(cl);
  945         }
  946         ASSERT(qlen(cl->cl_q) == 0);
  947 }
  948 
  949 /*
  950  * timestamp list support routines
  951  *
  952  * this implementation has been revamped and
  953  * now uses a TAILQ structure.
  954  * timestamp list holds class timestamps
  955  * there is one timestamp list per class.
  956  */
  957 static TSLIST *
  958 tslist_alloc(void)
  959 {
  960         TSLIST *list_init;
  961 
  962         list_init = malloc(sizeof(TSLIST), M_DEVBUF, M_WAITOK);
  963         TAILQ_INIT(list_init);
  964         return (list_init);
  965 }
  966 
  967 static void
  968 tslist_destroy(struct jobs_class *cl)
  969 {
  970         while (tslist_first(cl->arv_tm) != NULL)
  971                 tslist_dequeue(cl);
  972 
  973         free(cl->arv_tm, M_DEVBUF);
  974 }
  975 
  976 static int
  977 tslist_enqueue(struct jobs_class *cl, u_int64_t arv)
  978 {
  979         TSENTRY *pushed;
  980         pushed = malloc(sizeof(TSENTRY), M_DEVBUF, M_WAITOK);
  981         if (pushed == NULL)
  982                 return (0);     
  983 
  984         pushed->timestamp = arv;
  985         TAILQ_INSERT_TAIL(cl->arv_tm, pushed, ts_list);
  986         return (1);
  987 }
  988 
  989 static void
  990 tslist_dequeue(struct jobs_class *cl)
  991 {
  992         TSENTRY *popped;
  993         popped = tslist_first(cl->arv_tm);
  994         if (popped != NULL) {
  995                   TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
  996                   free(popped, M_DEVBUF);
  997         }
  998         return;
  999 }
 1000 
 1001 static void
 1002 tslist_drop(struct jobs_class *cl)
 1003 {
 1004         TSENTRY *popped;
 1005         popped = tslist_last(cl->arv_tm);
 1006         if (popped != NULL) {
 1007                   TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
 1008                   free(popped, M_DEVBUF);
 1009         }
 1010         return;
 1011 }
 1012 
 1013 /*
 1014  * rate allocation support routines
 1015  */
 1016 /*
 1017  * enforce_wc: enforce that backlogged classes have non-zero
 1018  * service rate, and that non-backlogged classes have zero
 1019  * service rate.
 1020  */
 1021 
 1022 static int
 1023 enforce_wc(struct jobs_if *jif)
 1024 {
 1025         struct jobs_class *cl;
 1026 
 1027         int64_t active_classes;
 1028         int pri;
 1029         int is_backlogged, class_exists, updated;
 1030 
 1031         updated = 0;
 1032         active_classes = 0;
 1033 
 1034         for (pri = 0; pri <= jif->jif_maxpri; pri++) {
 1035                 cl = jif->jif_classes[pri];
 1036                 class_exists = (cl != NULL);
 1037                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1038 
 1039                 if (is_backlogged)
 1040                         active_classes++;
 1041                 if ((is_backlogged && cl->service_rate <= 0)
 1042                     ||(class_exists
 1043                        && !is_backlogged && cl->service_rate > 0))
 1044                         updated = 1;
 1045         }
 1046 
 1047         if (updated) {
 1048                 for (pri = 0; pri <= jif->jif_maxpri; pri++) {
 1049                         cl = jif->jif_classes[pri];
 1050                         class_exists = (cl != NULL);
 1051                         is_backlogged = (class_exists && !qempty(cl->cl_q));
 1052 
 1053                         if (class_exists && !is_backlogged)
 1054                                 cl->service_rate = 0;
 1055                         else if (is_backlogged)
 1056                                 cl->service_rate = (int64_t)(bps_to_internal((u_int64_t)jif->jif_bandwidth)/active_classes);
 1057                 }
 1058         }
 1059 
 1060         return (updated);
 1061 }
 1062 
 1063 /*
 1064  * adjust_rates_rdc: compute the service rates adjustments
 1065  * needed to realize the desired proportional delay differentiation.
 1066  * essentially, the rate adjustement delta_rate = prop_control*error,
 1067  * where error is the difference between the measured "weighted"
 1068  * delay and the mean of the weighted delays. see paper for more
 1069  * information.
 1070  * prop_control has slightly changed since the INFOCOM paper,
 1071  * this condition seems to provide better results.
 1072  */
 1073 
 1074 static int64_t *
 1075 adjust_rates_rdc(struct jobs_if *jif)
 1076 {
 1077         int64_t *result;
 1078         int64_t credit, available, lower_bound, upper_bound;
 1079         int64_t bk;
 1080         int i, j;
 1081         int rdc_classes, active_classes;
 1082         int class_exists, is_backlogged;
 1083         struct jobs_class *cl;
 1084         int64_t *error;
 1085         int64_t prop_control;
 1086         u_int64_t max_prod;
 1087         u_int64_t min_share;
 1088         u_int64_t max_avg_pkt_size;
 1089 
 1090         /*
 1091          * min_share is scaled
 1092          * to avoid dealing with doubles
 1093          */
 1094         active_classes = 0;
 1095         rdc_classes = 0;
 1096         max_prod = 0;
 1097         max_avg_pkt_size = 0;
 1098 
 1099         upper_bound = (int64_t)jif->jif_bandwidth;
 1100 
 1101         for (i = 0; i <= jif->jif_maxpri; i++) {
 1102                 cl = jif->jif_classes[i];
 1103                 class_exists = (cl != NULL);
 1104                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1105                 if (is_backlogged) {
 1106                         active_classes++;
 1107                         if (cl->concerned_rdc)
 1108                                 rdc_classes++;
 1109                         else
 1110                                 upper_bound -=
 1111                                     internal_to_bps(cl->service_rate);
 1112                 }
 1113         }
 1114 
 1115         result = malloc((jif->jif_maxpri+1)*sizeof(int64_t),
 1116             M_DEVBUF, M_WAITOK);
 1117 
 1118         if (result == NULL)
 1119                 return NULL;
 1120 
 1121         for (i = 0; i <= jif->jif_maxpri; i++)
 1122                 result[i] = 0;
 1123 
 1124         if (upper_bound <= 0 || rdc_classes == 0)
 1125                 return result;
 1126 
 1127         credit = 0;
 1128         lower_bound = 0;
 1129         min_share = ((u_int64_t)1 << SCALE_SHARE);
 1130         bk = 0;
 1131 
 1132         for (i = 0; i <= jif->jif_maxpri; i++) {
 1133                 cl = jif->jif_classes[i];
 1134                 class_exists = (cl != NULL);
 1135                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1136                 if (is_backlogged && cl->concerned_rdc)
 1137                         bk += cl->cl_rin.bytes;
 1138         }
 1139 
 1140         if (bk == 0)
 1141                 return (result);
 1142 
 1143         for (i = 0; i <= jif->jif_maxpri; i++) {
 1144                 cl = jif->jif_classes[i];
 1145                 class_exists = (cl != NULL);
 1146                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1147                 if (is_backlogged
 1148                     && (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share)
 1149                         min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk;
 1150                 if (is_backlogged && cl->concerned_rdc
 1151                     && cl->delay_prod_others > max_prod)
 1152                         max_prod = cl->delay_prod_others;
 1153 
 1154                 if (is_backlogged && cl->concerned_rdc
 1155                     && cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets)
 1156                         max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets);
 1157         }
 1158 
 1159         error = update_error(jif);
 1160         if (!error)
 1161                 return (NULL);
 1162 
 1163         prop_control = (upper_bound*upper_bound*min_share)
 1164             /(max_prod*(max_avg_pkt_size << 2));
 1165   
 1166         prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */
 1167 
 1168         credit = 0;
 1169         for (i = 0; i <= jif->jif_maxpri; i++) {
 1170                 cl = jif->jif_classes[i];
 1171                 class_exists = (cl != NULL);
 1172                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1173                 if (is_backlogged && cl->concerned_rdc) {
 1174                         result[i] = -prop_control*error[i]; /* in BT-1 */
 1175                         result[i] >>= (SCALE_SHARE);
 1176                 }
 1177         }
 1178 
 1179         free(error, M_DEVBUF); /* we don't need these anymore */
 1180 
 1181         /* saturation */
 1182 
 1183         for (i = 0; i <= jif->jif_maxpri; i++) {
 1184                 cl = jif->jif_classes[i];
 1185                 class_exists = (cl != NULL);
 1186                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1187 
 1188                 if (is_backlogged && cl->concerned_rdc)
 1189                         lower_bound += cl->min_rate_adc;
 1190                 /*
 1191                  * note: if there's no ADC or ARC on cl,
 1192                  * this is equal to zero, which is fine
 1193                  */
 1194         }
 1195 
 1196         for (i = 0; i <= jif->jif_maxpri; i++) {
 1197                 cl = jif->jif_classes[i];
 1198                 class_exists = (cl != NULL);
 1199                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1200 
 1201                 if (is_backlogged && cl->concerned_rdc
 1202                     && result[i] + cl->service_rate > upper_bound) {
 1203                         for (j = 0; j <= jif->jif_maxpri; j++) {
 1204                                 cl = jif->jif_classes[j];
 1205                                 class_exists = (cl != NULL);
 1206                                 is_backlogged = (class_exists
 1207                                                  && !qempty(cl->cl_q));
 1208                                 if (is_backlogged && cl->concerned_rdc) {
 1209                                         if (j == i)
 1210                                                 result[j] = upper_bound
 1211                                                     -cl->service_rate
 1212                                                     + cl->min_rate_adc
 1213                                                     - lower_bound;
 1214                                         else
 1215                                                 result[j] =
 1216                                                     -cl->service_rate
 1217                                                     +cl->min_rate_adc;
 1218                                 }
 1219                         }
 1220                         return result;
 1221                 }
 1222 
 1223                 cl = jif->jif_classes[i];
 1224                 /* do this again since it may have been modified */
 1225                 class_exists = (cl != NULL);
 1226                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1227 
 1228                 if (is_backlogged && cl->concerned_rdc
 1229                     && result[i] + cl->service_rate < cl->min_rate_adc) {
 1230                         credit += cl->service_rate+result[i]
 1231                             -cl->min_rate_adc;
 1232                         /* "credit" is in fact a negative number */
 1233                         result[i] = -cl->service_rate+cl->min_rate_adc;
 1234                 }
 1235         }
 1236 
 1237         for (i = jif->jif_maxpri; (i >= 0 && credit < 0); i--) {
 1238                 cl = jif->jif_classes[i];
 1239                 class_exists = (cl != NULL);
 1240                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1241  
 1242                 if (is_backlogged && cl->concerned_rdc) {
 1243                         available = result[i]
 1244                             + cl->service_rate-cl->min_rate_adc;
 1245                         if (available >= -credit) {
 1246                                 result[i] += credit;
 1247                                 credit = 0;
 1248                         } else {
 1249                                 result[i] -= available;
 1250                                 credit += available;
 1251                         }
 1252                 }
 1253         }
 1254         return result;
 1255 }
 1256 
 1257 /*
 1258  * assign_rate_drops_adc: returns the adjustment needed to
 1259  * the service rates to meet the absolute delay/rate constraints
 1260  * (delay/throughput bounds) and drops traffic if need be.
 1261  * see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info.
 1262  */
 1263 
 1264 static int64_t *
 1265 assign_rate_drops_adc(struct jobs_if *jif)
 1266 {
 1267         int64_t *result;
 1268         int class_exists, is_backlogged;
 1269         struct jobs_class *cl;
 1270 
 1271         int64_t *c, *n, *k;
 1272         int64_t *available;
 1273 
 1274         int lowest, highest;
 1275         int keep_going;
 1276         int i;
 1277         u_int64_t now, oldest_arv;
 1278         int64_t remaining_time;
 1279         struct mbuf* pkt;
 1280         u_int64_t len;
 1281 
 1282         now = read_machclk();
 1283         oldest_arv = now;
 1284 
 1285         result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
 1286         if (result == NULL)
 1287                 return NULL;
 1288         c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
 1289         if (c == NULL)
 1290                 return NULL;
 1291         n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
 1292         if (n == NULL)
 1293                 return NULL;
 1294         k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
 1295         if (k == NULL)
 1296                 return NULL;
 1297         available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
 1298         if (available == NULL)
 1299                 return NULL;
 1300 
 1301         for (i = 0; i <= jif->jif_maxpri; i++)
 1302                 result[i] = 0;
 1303 
 1304         keep_going = 1;
 1305 
 1306         for (i = 0; i <= jif->jif_maxpri; i++) {
 1307                 cl = jif->jif_classes[i];
 1308                 class_exists = (cl != NULL);
 1309                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1310 
 1311                 if (is_backlogged) {
 1312                         if (cl->concerned_adc) {
 1313                                 /*
 1314                                  * get the arrival time of the oldest
 1315                                  * class-i packet
 1316                                  */
 1317                                 if (tslist_first(cl->arv_tm) == NULL)
 1318                                         oldest_arv = now; /* NOTREACHED */
 1319                                 else
 1320                                         oldest_arv = (tslist_first(cl->arv_tm))->timestamp;
 1321 
 1322                                 n[i] = cl->service_rate;
 1323                                 k[i] = scale_rate((int64_t)(cl->cl_rin.bytes - cl->cl_rout.bytes));
 1324 
 1325                                 remaining_time = cl->cl_adc
 1326                                     - (int64_t)delay_diff(now, oldest_arv);
 1327                                 if (remaining_time > 0) {
 1328                                         c[i] = remaining_time;
 1329                                         /*
 1330                                          * c is the remaining time before
 1331                                          * the deadline is violated
 1332                                          * (in ticks)
 1333                                          */
 1334                                         available[i] = n[i]-k[i]/c[i];
 1335                                 } else {
 1336                                         /*
 1337                                          * deadline has passed...
 1338                                          * we allocate the whole link
 1339                                          * capacity to hopefully
 1340                                          * solve the problem
 1341                                          */
 1342                                         c[i] = 0;
 1343                                         available[i] = -((int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth));
 1344                                 }
 1345                                 if (cl->concerned_arc) {
 1346                                         /*
 1347                                          * there's an ARC in addition
 1348                                          * to the ADC
 1349                                          */
 1350                                         if (n[i] - cl->cl_arc < available[i])
 1351                                                 available[i] = n[i]
 1352                                                     - cl->cl_arc;
 1353                                 }
 1354                         } else if (cl->concerned_arc) {
 1355                                 /*
 1356                                  * backlogged, concerned by ARC
 1357                                  * but not by ADC
 1358                                  */
 1359                                 n[i] = cl->service_rate;
 1360                                 available[i] = n[i] - cl->cl_arc;
 1361                         } else {
 1362                                 /*
 1363                                  * backlogged but not concerned by ADC
 1364                                  * or ARC -> can give everything
 1365                                  */
 1366                                 n[i] = cl->service_rate;
 1367                                 available[i] = n[i];
 1368                         }
 1369                 } else {
 1370                         /* not backlogged */
 1371                         n[i] = 0;
 1372                         k[i] = 0;
 1373                         c[i] = 0;
 1374                         if (class_exists)
 1375                                 available[i] = cl->service_rate;
 1376                         else
 1377                                 available[i] = 0;
 1378                 }
 1379         }
 1380 
 1381         /* step 1: adjust rates (greedy algorithm) */
 1382 
 1383         highest = 0;
 1384         lowest  = jif->jif_maxpri;
 1385 
 1386         while (highest < jif->jif_maxpri+1 && available[highest] >= 0)
 1387                 highest++; /* which is the highest class that needs more service? */
 1388         while (lowest > 0 && available[lowest] <= 0)
 1389                 lowest--;  /* which is the lowest class that needs less service? */
 1390 
 1391         while (highest != jif->jif_maxpri+1 && lowest != -1) {
 1392                 /* give the excess service from lowest to highest */
 1393                 if (available[lowest]+available[highest] > 0) {
 1394                         /*
 1395                          * still some "credit" left
 1396                          * give all that is needed by "highest"
 1397                          */
 1398                         n[lowest]  += available[highest];
 1399                         n[highest] -= available[highest];
 1400                         available[lowest]  += available[highest];
 1401                         available[highest] = 0;
 1402 
 1403                         while (highest < jif->jif_maxpri+1
 1404                                && available[highest] >= 0)
 1405                                 highest++;  /* which is the highest class that needs more service now? */
 1406 
 1407                 } else if (available[lowest]+available[highest] == 0) {
 1408                         /* no more credit left but it's fine */
 1409                         n[lowest]  += available[highest];
 1410                         n[highest] -= available[highest];
 1411                         available[highest] = 0;
 1412                         available[lowest]  = 0;
 1413 
 1414                         while (highest < jif->jif_maxpri+1
 1415                                && available[highest] >= 0)
 1416                                 highest++;  /* which is the highest class that needs more service? */
 1417                         while (lowest >= 0 && available[lowest] <= 0)
 1418                                 lowest--;   /* which is the lowest class that needs less service? */
 1419 
 1420                 } else if (available[lowest]+available[highest] < 0) {
 1421                         /*
 1422                          * no more credit left and we need to switch
 1423                          * to another class
 1424                          */
 1425                         n[lowest]  -= available[lowest];
 1426                         n[highest] += available[lowest];
 1427                         available[highest] += available[lowest];
 1428                         available[lowest]  = 0;
 1429 
 1430                         while ((lowest >= 0)&&(available[lowest] <= 0))
 1431                                 lowest--;  /* which is the lowest class that needs less service? */
 1432                 }
 1433         }
 1434 
 1435         for (i = 0; i <= jif->jif_maxpri; i++) {
 1436                 cl = jif->jif_classes[i];
 1437                 class_exists = (cl != NULL);
 1438                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1439                 if (is_backlogged) {
 1440                         result[i] = n[i] - cl->service_rate;
 1441                 } else {
 1442                         if (class_exists)
 1443                                 result[i] = - cl->service_rate;
 1444                         else
 1445                                 result[i] = 0;
 1446                 }
 1447         }
 1448 
 1449         /* step 2: adjust drops (for ADC) */
 1450 
 1451         if (highest != jif->jif_maxpri+1) {
 1452                 /* some class(es) still need(s) additional service */
 1453                 for (i = 0; i <= jif->jif_maxpri; i++) {
 1454                         cl = jif->jif_classes[i];
 1455                         class_exists = (cl != NULL);
 1456                         is_backlogged = (class_exists
 1457                                          && !qempty(cl->cl_q));
 1458                         if (is_backlogged && available[i] < 0) {
 1459                                 if (cl->concerned_adc) {
 1460                                         k[i] = c[i]*n[i];
 1461                                         while (keep_going && scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes)) > k[i]) {
 1462                                                 pkt = qtail(cl->cl_q);
 1463                                                 if (pkt != NULL) {
 1464                                                         /* "safeguard" test (a packet SHOULD be in there) */
 1465                                                         len = (u_int64_t)m_pktlen(pkt);
 1466                                                         /* access packet at the tail */
 1467                                                         if (cl->concerned_alc
 1468                                                             && cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
 1469                                                                 keep_going = 0; /* relax ADC in favor of ALC */
 1470                                                         } else {
 1471                                                                 /* drop packet at the tail of the class-i queue, update values */
 1472                                                                 pkt = _getq_tail(cl->cl_q);
 1473                                                                 len = (u_int64_t)m_pktlen(pkt);
 1474                                                                 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
 1475                                                                 PKTCNTR_SUB(&cl->cl_rin, (int)len);
 1476                                                                 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
 1477                                                                 PKTCNTR_SUB(&cl->st_rin, (int)len);
 1478                                                                 cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
 1479                                                                 m_freem(pkt); /* the packet is trashed here */
 1480                                                                 tslist_drop(cl);
 1481                                                                 IFQ_DEC_LEN(cl->cl_jif->jif_ifq);
 1482                                                         }
 1483                                                 } else
 1484                                                         keep_going = 0; /* NOTREACHED */
 1485                                         }
 1486                                         k[i] = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes));
 1487                                 }
 1488                                 /*
 1489                                  * n[i] is the max rate we can give.
 1490                                  * the above drops as much as possible
 1491                                  * to respect a delay bound.
 1492                                  * for throughput bounds,
 1493                                  * there's nothing that can be done
 1494                                  * after the greedy reallocation.
 1495                                  */
 1496                         }
 1497                 }
 1498         }
 1499 
 1500         /* update the values of min_rate_adc */
 1501         for (i = 0; i <= jif->jif_maxpri; i++) {
 1502                 cl = jif->jif_classes[i];
 1503                 class_exists = (cl != NULL);
 1504                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1505                 if (is_backlogged && cl->concerned_adc) {
 1506                         if (c[i] != 0) {
 1507                                 if (cl->concerned_adc
 1508                                     && !cl->concerned_arc)
 1509                                         cl->min_rate_adc = k[i]/c[i];
 1510                                 else
 1511                                         cl->min_rate_adc = n[i];
 1512                         } else
 1513                                 cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
 1514                 } else if (is_backlogged && cl->concerned_arc)
 1515                         cl->min_rate_adc = n[i]; /* the best we can give */
 1516                 else {
 1517                         if (class_exists)
 1518                                 cl->min_rate_adc = 0;
 1519                 }
 1520         }
 1521 
 1522         free(c, M_DEVBUF);
 1523         free(n, M_DEVBUF);
 1524         free(k, M_DEVBUF);
 1525         free(available, M_DEVBUF);
 1526 
 1527         return (result);
 1528 }
 1529 
 1530 /*
 1531  * update_error: returns the difference between the mean weighted
 1532  * delay and the weighted delay for each class. if proportional
 1533  * delay differentiation is perfectly achieved, it should return
 1534  * zero for each class.
 1535  */
 1536 static int64_t *
 1537 update_error(struct jobs_if *jif)
 1538 {
 1539         int i;
 1540         int active_classes, backlogged_classes;
 1541         u_int64_t mean_weighted_delay;
 1542         u_int64_t delays[JOBS_MAXPRI];
 1543         int64_t* error;
 1544         int class_exists, is_backlogged;
 1545         struct jobs_class *cl;
 1546 
 1547         error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1), M_DEVBUF,
 1548             M_WAITOK|M_ZERO);
 1549 
 1550         if (error == NULL)
 1551                 return NULL;
 1552 
 1553         mean_weighted_delay = 0;
 1554         active_classes = 0;
 1555         backlogged_classes = 0;
 1556 
 1557         for (i = 0; i <= jif->jif_maxpri; i++) {
 1558                 cl = jif->jif_classes[i];
 1559                 class_exists = (cl != NULL);
 1560                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1561 
 1562                 if (is_backlogged) {
 1563                         backlogged_classes++;
 1564                         if (cl->concerned_rdc) {
 1565                                 delays[i] = proj_delay(jif, i);
 1566                                 mean_weighted_delay += cl->delay_prod_others*delays[i];
 1567                                 active_classes ++;
 1568                         }
 1569                 }
 1570         }
 1571 
 1572         if (active_classes == 0)
 1573                 return error;
 1574         else
 1575                 mean_weighted_delay /= active_classes;
 1576 
 1577         for (i = 0; i <= jif->jif_maxpri; i++) {
 1578                 cl = jif->jif_classes[i];
 1579                 class_exists = (cl != NULL);
 1580                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1581 
 1582                 if (is_backlogged && cl->concerned_rdc)
 1583                         error[i] = ((int64_t)mean_weighted_delay)-((int64_t)cl->delay_prod_others*delays[i]);
 1584                 else
 1585                         error[i] = 0; /*
 1586                                        * either the class isn't concerned,
 1587                                        * or it's not backlogged.
 1588                                        * in any case, the rate shouldn't
 1589                                        * be adjusted.
 1590                                        */
 1591         }
 1592         return error;
 1593 }
 1594 
 1595 /*
 1596  * min_rates_adc: computes the minimum service rates needed in
 1597  * each class to meet the absolute delay bounds. if, for any
 1598  * class i, the current service rate of class i is less than
 1599  * the computed minimum service rate, this function returns
 1600  * false, true otherwise.
 1601  */
 1602 static int
 1603 min_rates_adc(struct jobs_if *jif)
 1604 {
 1605         int result;
 1606         int i;
 1607         int class_exists, is_backlogged;
 1608         int64_t remaining_time;
 1609         struct jobs_class *cl;
 1610         result = 1;
 1611 
 1612         for (i = 0; i <= jif->jif_maxpri; i++) {
 1613                 cl = jif->jif_classes[i];
 1614                 class_exists = (cl != NULL);
 1615                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1616                 if (is_backlogged && cl->concerned_adc) { 
 1617                         remaining_time = cl->cl_adc - proj_delay(jif, i);
 1618                         if (remaining_time > 0 ) {
 1619                                 /* min rate needed for ADC */
 1620                                 cl->min_rate_adc = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes))/remaining_time;
 1621                                 if (cl->concerned_arc
 1622                                     && cl->cl_arc > cl->min_rate_adc) {
 1623                                         /* min rate needed for ADC + ARC */
 1624                                         cl->min_rate_adc = cl->cl_arc;
 1625                                 }
 1626                         } else {
 1627                                 /* the deadline has been exceeded: give the whole link capacity to hopefully fix the situation */
 1628                                 cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
 1629                         }
 1630                 } else if (is_backlogged && cl->concerned_arc)
 1631                         cl->min_rate_adc = cl->cl_arc;                  /* no ADC, an ARC */
 1632                 else if (class_exists)
 1633                         cl->min_rate_adc = 0;   /*
 1634                                                  * either the class is not
 1635                                                  * backlogged
 1636                                                  * or there is no ADC and
 1637                                                  * no ARC
 1638                                                  */
 1639                 if (is_backlogged && cl->min_rate_adc > cl->service_rate)
 1640                         result = 0;
 1641         }
 1642 
 1643         return result;
 1644 }
 1645 
 1646 /*
 1647  * proj_delay: computes the difference between the current time
 1648  * and the time the oldest class-i packet still in the class-i
 1649  * queue i arrived in the system.
 1650  */
 1651 static int64_t
 1652 proj_delay(struct jobs_if *jif, int i)
 1653 {
 1654         u_int64_t now;
 1655         int class_exists, is_backlogged;
 1656         struct jobs_class *cl;
 1657 
 1658         now = read_machclk();
 1659         cl = jif->jif_classes[i];
 1660         class_exists = (cl != NULL);
 1661         is_backlogged = (class_exists && !qempty(cl->cl_q));
 1662 
 1663         if (is_backlogged)
 1664                 return ((int64_t)delay_diff(now, tslist_first(cl->arv_tm)->timestamp));
 1665 
 1666         return (0); /* NOTREACHED */
 1667 }
 1668 
 1669 /*
 1670  * pick_dropped_rlc: returns the class index of the class to be
 1671  * dropped for meeting the relative loss constraints.
 1672  */
 1673 static int
 1674 pick_dropped_rlc(struct jobs_if *jif)
 1675 {
 1676         int64_t mean;
 1677         int64_t* loss_error;
 1678         int i, active_classes, backlogged_classes;
 1679         int class_exists, is_backlogged;
 1680         int class_dropped;
 1681         int64_t max_error;
 1682         int64_t max_alc;
 1683         struct mbuf* pkt;
 1684         struct jobs_class *cl;
 1685         u_int64_t len;
 1686 
 1687         loss_error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1),
 1688             M_DEVBUF, M_WAITOK);
 1689 
 1690         if (loss_error == NULL)
 1691                 return -1;
 1692 
 1693         class_dropped = -1;
 1694         max_error = 0;
 1695         mean = 0;
 1696         active_classes = 0;
 1697         backlogged_classes = 0;
 1698 
 1699         for (i = 0; i <= jif->jif_maxpri; i++) {
 1700                 cl = jif->jif_classes[i];
 1701                 class_exists = (cl != NULL);
 1702                 is_backlogged = (class_exists && !qempty(cl->cl_q));
 1703                 if (is_backlogged) {
 1704                         backlogged_classes ++;
 1705                         if (cl->concerned_rlc) {
 1706                                 mean += cl->loss_prod_others
 1707                                     * cl->current_loss;
 1708                                 active_classes++;
 1709                         }
 1710                 }
 1711         }
 1712 
 1713         if (active_classes > 0)
 1714                 mean /= active_classes;
 1715 
 1716         if (active_classes == 0)
 1717                 class_dropped = JOBS_MAXPRI+1; /*
 1718                                                 * no classes are concerned
 1719                                                 * by RLCs (JOBS_MAXPRI+1
 1720                                                 * means "ignore RLC" here)
 1721                                                 */
 1722         else {
 1723                 for (i = 0; i <= jif->jif_maxpri; i++) {
 1724                         cl = jif->jif_classes[i];
 1725                         class_exists = (cl != NULL);
 1726                         is_backlogged = (class_exists
 1727                                          && !qempty(cl->cl_q));
 1728 
 1729                         if ((is_backlogged)&&(cl->cl_rlc))
 1730                                 loss_error[i]=cl->loss_prod_others
 1731                                     *cl->current_loss-mean;
 1732                         else
 1733                                 loss_error[i] = ALTQ_INFINITY;
 1734                 }
 1735 
 1736                 for (i = 0; i <= jif->jif_maxpri; i++) {
 1737                         cl = jif->jif_classes[i];
 1738                         class_exists = (cl != NULL);
 1739                         is_backlogged = (class_exists
 1740                                          && !qempty(cl->cl_q));
 1741                         if (is_backlogged && loss_error[i] <= max_error) {
 1742                                 /*
 1743                                  * find out which class is the most
 1744                                  * below the mean.
 1745                                  * it's the one that needs to be dropped
 1746                                  * ties are broken in favor of the higher
 1747                                  * priority classes (i.e., if two classes
 1748                                  * present the same deviation, the lower
 1749                                  * priority class will get dropped).
 1750                                  */
 1751                                 max_error = loss_error[i];
 1752                                 class_dropped = i;
 1753                         }
 1754                 }
 1755 
 1756                 if (class_dropped != -1) {
 1757                         cl = jif->jif_classes[class_dropped];
 1758                         pkt = qtail(cl->cl_q);
 1759                         if (pkt != NULL) {
 1760                                 /*
 1761                                  * "safeguard" test (a packet SHOULD be
 1762                                  * in there)
 1763                                  */
 1764                                 len = (u_int64_t)m_pktlen(pkt);
 1765                                 /* access packet at the tail */
 1766                                 if (cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
 1767                                         /*
 1768                                          * the class to drop for meeting
 1769                                          * the RLC will defeat the ALC:
 1770                                          * ignore RLC.
 1771                                          */
 1772                                         class_dropped = JOBS_MAXPRI+1;
 1773                                 }
 1774                         } else
 1775                                 class_dropped = JOBS_MAXPRI+1; /* NOTREACHED */
 1776                 } else
 1777                         class_dropped = JOBS_MAXPRI+1;
 1778         }
 1779 
 1780         if (class_dropped == JOBS_MAXPRI+1) {
 1781                 max_alc = -((int64_t)1 << SCALE_LOSS);
 1782                 for (i = jif->jif_maxpri; i >= 0; i--) {
 1783                         cl = jif->jif_classes[i];
 1784                         class_exists = (cl != NULL);
 1785                         is_backlogged = (class_exists
 1786                                          && !qempty(cl->cl_q));
 1787                         if (is_backlogged) {
 1788                                 if (cl->concerned_alc && cl->cl_alc - cl->current_loss > max_alc) {
 1789                                         max_alc = cl->cl_alc-cl->current_loss; /* pick the class which is the furthest from its ALC */
 1790                                         class_dropped = i;
 1791                                 } else if (!cl->concerned_alc && ((int64_t) 1 << SCALE_LOSS)-cl->current_loss > max_alc) {
 1792                                         max_alc = ((int64_t) 1 << SCALE_LOSS)-cl->current_loss;
 1793                                         class_dropped = i;
 1794                                 }
 1795                         }
 1796                 }
 1797         }
 1798 
 1799         free(loss_error, M_DEVBUF);
 1800         return (class_dropped);
 1801 }
 1802 
 1803 /*
 1804  * ALTQ binding/setup functions
 1805  */
 1806 /*
 1807  * jobs device interface
 1808  */
 1809 int
 1810 jobsopen(dev_t dev, int flag, int fmt,
 1811     struct lwp *l)
 1812 {
 1813         if (machclk_freq == 0)
 1814                 init_machclk();
 1815 
 1816         if (machclk_freq == 0) {
 1817                 printf("jobs: no CPU clock available!\n");
 1818                 return (ENXIO);
 1819         }
 1820         /* everything will be done when the queueing scheme is attached. */
 1821         return 0;
 1822 }
 1823 
 1824 int
 1825 jobsclose(dev_t dev, int flag, int fmt,
 1826     struct lwp *l)
 1827 {
 1828         struct jobs_if *jif;
 1829         int err, error = 0;
 1830 
 1831         while ((jif = jif_list) != NULL) {
 1832                 /* destroy all */
 1833                 if (ALTQ_IS_ENABLED(jif->jif_ifq))
 1834                         altq_disable(jif->jif_ifq);
 1835 
 1836                 err = altq_detach(jif->jif_ifq);
 1837                 if (err == 0)
 1838                         err = jobs_detach(jif);
 1839                 if (err != 0 && error == 0)
 1840                         error = err;
 1841         }
 1842 
 1843         return error;
 1844 }
 1845 
 1846 int
 1847 jobsioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag,
 1848     struct lwp *l)
 1849 {
 1850         struct jobs_if *jif;
 1851         struct jobs_interface *ifacep;
 1852         struct proc *p = l->l_proc;
 1853         int     error = 0;
 1854 
 1855         /* check super-user privilege */
 1856         switch (cmd) {
 1857         case JOBS_GETSTATS:
 1858                 break;
 1859         default:
 1860 #if (__FreeBSD_version > 400000)
 1861                 if ((error = suser(p)) != 0)
 1862                         return (error);
 1863 #else
 1864                 if ((error = kauth_authorize_network(p->p_cred,
 1865                     KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_JOBS, NULL,
 1866                     NULL, NULL)) != 0)
 1867                         return (error);
 1868 #endif
 1869                 break;
 1870         }
 1871 
 1872         switch (cmd) {
 1873 
 1874         case JOBS_IF_ATTACH:
 1875                 error = jobscmd_if_attach((struct jobs_attach *)addr);
 1876                 break;
 1877 
 1878         case JOBS_IF_DETACH:
 1879                 error = jobscmd_if_detach((struct jobs_interface *)addr);
 1880                 break;
 1881 
 1882         case JOBS_ENABLE:
 1883         case JOBS_DISABLE:
 1884         case JOBS_CLEAR:
 1885                 ifacep = (struct jobs_interface *)addr;
 1886                 if ((jif = altq_lookup(ifacep->jobs_ifname,
 1887                                        ALTQT_JOBS)) == NULL) {
 1888                         error = EBADF;
 1889                         break;
 1890                 }
 1891 
 1892                 switch (cmd) {
 1893                 case JOBS_ENABLE:
 1894                         if (jif->jif_default == NULL) {
 1895 #if 1
 1896                                 printf("jobs: no default class\n");
 1897 #endif
 1898                                 error = EINVAL;
 1899                                 break;
 1900                         }
 1901                         error = altq_enable(jif->jif_ifq);
 1902                         break;
 1903 
 1904                 case JOBS_DISABLE:
 1905                         error = altq_disable(jif->jif_ifq);
 1906                         break;
 1907 
 1908                 case JOBS_CLEAR:
 1909                         jobs_clear_interface(jif);
 1910                         break;
 1911                 }
 1912                 break;
 1913 
 1914                 case JOBS_ADD_CLASS:
 1915                         error = jobscmd_add_class((struct jobs_add_class *)addr);
 1916                         break;
 1917 
 1918         case JOBS_DEL_CLASS:
 1919                 error = jobscmd_delete_class((struct jobs_delete_class *)addr);
 1920                 break;
 1921 
 1922         case JOBS_MOD_CLASS:
 1923                 error = jobscmd_modify_class((struct jobs_modify_class *)addr);
 1924                 break;
 1925 
 1926         case JOBS_ADD_FILTER:
 1927                 error = jobscmd_add_filter((struct jobs_add_filter *)addr);
 1928                 break;
 1929 
 1930         case JOBS_DEL_FILTER:
 1931                 error = jobscmd_delete_filter((struct jobs_delete_filter *)addr);
 1932                 break;
 1933 
 1934         case JOBS_GETSTATS:
 1935                 error = jobscmd_class_stats((struct jobs_class_stats *)addr);
 1936                 break;
 1937 
 1938         default:
 1939                 error = EINVAL;
 1940                 break;
 1941         }
 1942         return error;
 1943 }
 1944 
 1945 static int
 1946 jobscmd_if_attach(struct jobs_attach *ap)
 1947 {
 1948         struct jobs_if *jif;
 1949         struct ifnet *ifp;
 1950         int error;
 1951 
 1952         if ((ifp = ifunit(ap->iface.jobs_ifname)) == NULL)
 1953                 return (ENXIO);
 1954         if ((jif = jobs_attach(&ifp->if_snd, ap->bandwidth, ap->qlimit, ap->separate)) == NULL)
 1955                 return (ENOMEM);
 1956 
 1957         /*
 1958          * set JOBS to this ifnet structure.
 1959          */
 1960         if ((error = altq_attach(&ifp->if_snd, ALTQT_JOBS, jif,
 1961                                  jobs_enqueue, jobs_dequeue, jobs_request,
 1962                                  &jif->jif_classifier, acc_classify)) != 0)
 1963                 (void)jobs_detach(jif);
 1964 
 1965         return (error);
 1966 }
 1967 
 1968 static int
 1969 jobscmd_if_detach(struct jobs_interface *ap)
 1970 {
 1971         struct jobs_if *jif;
 1972         int error;
 1973 
 1974         if ((jif = altq_lookup(ap->jobs_ifname, ALTQT_JOBS)) == NULL)
 1975                 return (EBADF);
 1976 
 1977         if (ALTQ_IS_ENABLED(jif->jif_ifq))
 1978                 altq_disable(jif->jif_ifq);
 1979 
 1980         if ((error = altq_detach(jif->jif_ifq)))
 1981                 return (error);
 1982 
 1983         return jobs_detach(jif);
 1984 }
 1985 
 1986 static int
 1987 jobscmd_add_class(struct jobs_add_class *ap)
 1988 {
 1989         struct jobs_if *jif;
 1990         struct jobs_class *cl;
 1991 
 1992         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 1993                 return (EBADF);
 1994 
 1995         if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
 1996                 return (EINVAL);
 1997 
 1998         if ((cl = jobs_class_create(jif, ap->pri,
 1999                                     ap->cl_adc, ap->cl_rdc,
 2000                                     ap->cl_alc, ap->cl_rlc, ap-> cl_arc,
 2001                                     ap->flags)) == NULL)
 2002                 return (ENOMEM);
 2003 
 2004         /* return a class handle to the user */
 2005         ap->class_handle = clp_to_clh(cl);
 2006         return (0);
 2007 }
 2008 
 2009 static int
 2010 jobscmd_delete_class(struct jobs_delete_class *ap)
 2011 {
 2012         struct jobs_if *jif;
 2013         struct jobs_class *cl;
 2014 
 2015         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 2016                 return (EBADF);
 2017 
 2018         if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
 2019                 return (EINVAL);
 2020 
 2021         return jobs_class_destroy(cl);
 2022 }
 2023 
 2024 static int
 2025 jobscmd_modify_class(struct jobs_modify_class *ap)
 2026 {
 2027         struct jobs_if *jif;
 2028         struct jobs_class *cl;
 2029 
 2030         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 2031                 return (EBADF);
 2032 
 2033         if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
 2034                 return (EINVAL);
 2035 
 2036         if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
 2037                 return (EINVAL);
 2038 
 2039         /*
 2040          * if priority is changed, move the class to the new priority
 2041          */
 2042         if (jif->jif_classes[ap->pri] != cl) {
 2043                 if (jif->jif_classes[ap->pri] != NULL)
 2044                         return (EEXIST);
 2045                 jif->jif_classes[cl->cl_pri] = NULL;
 2046                 jif->jif_classes[ap->pri] = cl;
 2047                 cl->cl_pri = ap->pri;
 2048         }
 2049 
 2050         /* call jobs_class_create to change class parameters */
 2051         if ((cl = jobs_class_create(jif, ap->pri,
 2052                                     ap->cl_adc, ap->cl_rdc,
 2053                                     ap->cl_alc, ap->cl_rlc, ap->cl_arc,
 2054                                     ap->flags)) == NULL)
 2055                 return (ENOMEM);
 2056         return 0;
 2057 }
 2058 
 2059 static int
 2060 jobscmd_add_filter(struct jobs_add_filter *ap)
 2061 {
 2062         struct jobs_if *jif;
 2063         struct jobs_class *cl;
 2064 
 2065         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 2066                 return (EBADF);
 2067 
 2068         if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
 2069                 return (EINVAL);
 2070 
 2071         return acc_add_filter(&jif->jif_classifier, &ap->filter,
 2072                               cl, &ap->filter_handle);
 2073 }
 2074 
 2075 static int
 2076 jobscmd_delete_filter(struct jobs_delete_filter *ap)
 2077 {
 2078         struct jobs_if *jif;
 2079 
 2080         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 2081                 return (EBADF);
 2082 
 2083         return acc_delete_filter(&jif->jif_classifier, ap->filter_handle);
 2084 }
 2085 
 2086 static int
 2087 jobscmd_class_stats(struct jobs_class_stats *ap)
 2088 {
 2089         struct jobs_if *jif;
 2090         struct jobs_class *cl;
 2091         struct class_stats stats, *usp;
 2092         int pri, error;
 2093 
 2094         if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
 2095                 return (EBADF);
 2096 
 2097         ap->maxpri = jif->jif_maxpri;
 2098 
 2099         /* then, read the next N classes */
 2100         usp = ap->stats;
 2101         for (pri = 0; pri <= jif->jif_maxpri; pri++) {
 2102                 cl = jif->jif_classes[pri];
 2103                 if (cl != NULL)
 2104                         get_class_stats(&stats, cl);
 2105                 else
 2106                         (void)memset(&stats, 0, sizeof(stats));
 2107                 if ((error = copyout((void *)&stats, (void *)usp++,
 2108                                      sizeof(stats))) != 0)
 2109                         return (error);
 2110         }
 2111         return (0);
 2112 }
 2113 
 2114 static void
 2115 get_class_stats(struct class_stats *sp, struct jobs_class *cl)
 2116 {
 2117         u_int64_t now;
 2118         now = read_machclk();
 2119 
 2120         sp->class_handle = clp_to_clh(cl);
 2121         sp->qlength = qlen(cl->cl_q);
 2122 
 2123         sp->period = cl->cl_period;
 2124         sp->rin = cl->st_rin;
 2125         sp->arrival = cl->st_arrival;
 2126         sp->arrivalbusy = cl->cl_arrival;
 2127         sp->rout = cl->st_rout;
 2128         sp->dropcnt = cl->cl_dropcnt;
 2129 
 2130         /*  PKTCNTR_RESET(&cl->st_arrival);*/
 2131         PKTCNTR_RESET(&cl->st_rin);
 2132         PKTCNTR_RESET(&cl->st_rout);
 2133 
 2134         sp->totallength = cl->cl_jif->jif_ifq->ifq_len;
 2135         sp->lastdel = ticks_to_secs(GRANULARITY*cl->cl_lastdel);
 2136         sp->avgdel = cl->cl_avgdel;
 2137 
 2138         cl->cl_avgdel = 0;
 2139 
 2140         sp->busylength = ticks_to_secs(1000*delay_diff(now, cl->idletime));
 2141         sp->adc_violations = cl->adc_violations;
 2142 
 2143         sp->wc_cycles_enqueue = cl->cl_jif->wc_cycles_enqueue;
 2144         sp->wc_cycles_dequeue = cl->cl_jif->wc_cycles_dequeue;
 2145         sp->bc_cycles_enqueue = cl->cl_jif->bc_cycles_enqueue;
 2146         sp->bc_cycles_dequeue = cl->cl_jif->bc_cycles_dequeue;
 2147         sp->avg_cycles_enqueue = cl->cl_jif->avg_cycles_enqueue;
 2148         sp->avg_cycles_dequeue = cl->cl_jif->avg_cycles_dequeue;
 2149         sp->avg_cycles2_enqueue = cl->cl_jif->avg_cycles2_enqueue;
 2150         sp->avg_cycles2_dequeue = cl->cl_jif->avg_cycles2_dequeue;
 2151         sp->total_enqueued = cl->cl_jif->total_enqueued;
 2152         sp->total_dequeued = cl->cl_jif->total_dequeued;
 2153 }
 2154 
 2155 /* convert a class handle to the corresponding class pointer */
 2156 static struct jobs_class *
 2157 clh_to_clp(struct jobs_if *jif, u_long chandle)
 2158 {
 2159         struct jobs_class *cl;
 2160 
 2161         cl = (struct jobs_class *)chandle;
 2162         if (chandle != ALIGN(cl)) {
 2163 #if 1
 2164                 printf("clh_to_cl: unaligned pointer %p\n", cl);
 2165 #endif
 2166                 return (NULL);
 2167         }
 2168 
 2169         if (cl == NULL || cl->cl_handle != chandle || cl->cl_jif != jif)
 2170                 return (NULL);
 2171         return (cl);
 2172 }
 2173 
 2174 /* convert a class pointer to the corresponding class handle */
 2175 static u_long
 2176 clp_to_clh(struct jobs_class *cl)
 2177 {
 2178         return (cl->cl_handle);
 2179 }
 2180 
 2181 #ifdef KLD_MODULE
 2182 
 2183 static struct altqsw jobs_sw =
 2184         {"jobs", jobsopen, jobsclose, jobsioctl};
 2185 
 2186 ALTQ_MODULE(altq_jobs, ALTQT_JOBS, &jobs_sw);
 2187 
 2188 #endif /* KLD_MODULE */
 2189 
 2190 #endif /* ALTQ3_COMPAT */
 2191 #endif /* ALTQ_JOBS */

Cache object: cecd34c2549125f267279ac9a4f30373


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.