The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ 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  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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