* Copyright (c) 2001, the Rector and Board of Visitors of the

/* $NetBSD: altq_jobs.c,v 1.14 2025/01/08 13:00:04 joe Exp $ */
/* $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */
/*
* Copyright (c) 2001, the Rector and Board of Visitors of the
* University of Virginia.
* All rights reserved.
*
* Redistribution and use in source and binary forms,
* with or without modification, are permitted provided
* that the following conditions are met:
*
* Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* Neither the name of the University of Virginia nor the names
* of its contributors may be used to endorse or promote products
* derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
* OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
* IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
* THE POSSIBILITY OF SUCH DAMAGE.
*/
/*
* JoBS - altq prototype implementation
*
* Author: Nicolas Christin <[email protected]>
*
* JoBS algorithms originally devised and proposed by
* Nicolas Christin and Jorg Liebeherr.
* Grateful acknowledgments to Tarek Abdelzaher for his help and
* comments, and to Kenjiro Cho for some helpful advice.
* Contributed by the Multimedia Networks Group at the University
* of Virginia.
*
* Papers and additional info can be found at
* http://qosbox.cs.virginia.edu
*
*/

/*
* JoBS queue
*/

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.14 2025/01/08 13:00:04 joe Exp $");

#ifdef _KERNEL_OPT
#include "opt_altq.h"
#include "opt_inet.h"
#endif

#ifdef ALTQ_JOBS /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */

#include <sys/param.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/socket.h>
#include <sys/sockio.h>
#include <sys/systm.h>
#include <sys/proc.h>
#include <sys/errno.h>
#include <sys/kernel.h>
#include <sys/queue.h>
#include <sys/kauth.h>

#ifdef __FreeBSD__
#include <sys/limits.h>
#endif

#include <net/if.h>
#include <net/if_types.h>

#include <altq/altq.h>
#include <altq/altq_conf.h>
#include <altq/altq_jobs.h>

#ifdef ALTQ3_COMPAT
/*
* function prototypes
*/
static struct jobs_if *jobs_attach(struct ifaltq *, u_int, u_int, u_int);
static void jobs_detach(struct jobs_if *);
static int jobs_clear_interface(struct jobs_if *);
static int jobs_request(struct ifaltq *, int, void *);
static void jobs_purge(struct jobs_if *);
static struct jobs_class *jobs_class_create(struct jobs_if *,
int, int64_t, int64_t, int64_t, int64_t, int64_t, int);
static int jobs_class_destroy(struct jobs_class *);
static int jobs_enqueue(struct ifaltq *, struct mbuf *);
static struct mbuf *jobs_dequeue(struct ifaltq *, int);

static int jobs_addq(struct jobs_class *, struct mbuf *, struct jobs_if*);
static struct mbuf *jobs_getq(struct jobs_class *);
static struct mbuf *jobs_pollq(struct jobs_class *);
static void jobs_purgeq(struct jobs_class *);

static int jobscmd_if_attach(struct jobs_attach *);
static int jobscmd_if_detach(struct jobs_interface *);
static int jobscmd_add_class(struct jobs_add_class *);
static int jobscmd_delete_class(struct jobs_delete_class *);
static int jobscmd_modify_class(struct jobs_modify_class *);
static int jobscmd_add_filter(struct jobs_add_filter *);
static int jobscmd_delete_filter(struct jobs_delete_filter *);
static int jobscmd_class_stats(struct jobs_class_stats *);
static void get_class_stats(struct class_stats *, struct jobs_class *);
static struct jobs_class *clh_to_clp(struct jobs_if *, u_long);
static u_long clp_to_clh(struct jobs_class *);

static TSLIST *tslist_alloc(void);
static void tslist_destroy(struct jobs_class *);
static int tslist_enqueue(struct jobs_class *, u_int64_t);
static void tslist_dequeue(struct jobs_class *);
static void tslist_drop(struct jobs_class *);

static int enforce_wc(struct jobs_if *);
static int64_t* adjust_rates_rdc(struct jobs_if *);
static int64_t* assign_rate_drops_adc(struct jobs_if *);
static int64_t* update_error(struct jobs_if *);
static int min_rates_adc(struct jobs_if *);
static int64_t proj_delay(struct jobs_if *, int);
static int pick_dropped_rlc(struct jobs_if *);

altqdev_decl(jobs);

/* jif_list keeps all jobs_if's allocated. */
static struct jobs_if *jif_list = NULL;

typedef unsigned long long ull;

/* setup functions */

static struct jobs_if *
jobs_attach(struct ifaltq *ifq, u_int bandwidth, u_int qlimit, u_int separate)
{
struct jobs_if *jif;

jif = malloc(sizeof(struct jobs_if), M_DEVBUF, M_WAITOK|M_ZERO);
if (jif == NULL)
return NULL;

jif->jif_bandwidth = bandwidth;
jif->jif_qlimit = qlimit;
jif->jif_separate = separate;
#ifdef ALTQ_DEBUG
printf("JoBS bandwidth = %d bps\n", (int)bandwidth);
printf("JoBS buffer size = %d pkts [%s]\n",
(int)qlimit, separate?"separate buffers":"shared buffer");
#endif
jif->jif_maxpri = -1;
jif->jif_ifq = ifq;

jif->wc_cycles_enqueue = 0;
jif->avg_cycles_enqueue = 0;
jif->avg_cycles2_enqueue = 0;
jif->bc_cycles_enqueue = ALTQ_INFINITY;
jif->wc_cycles_dequeue = 0;
jif->avg_cycles_dequeue = 0;
jif->avg_cycles2_dequeue = 0;
jif->bc_cycles_dequeue = ALTQ_INFINITY;
jif->total_enqueued = 0;
jif->total_dequeued = 0;

/* add this state to the jobs list */
jif->jif_next = jif_list;
jif_list = jif;

return jif;
}

static void
jobs_detach(struct jobs_if *jif)
{
(void)jobs_clear_interface(jif);

/* remove this interface from the jif list */
if (jif_list == jif)
jif_list = jif->jif_next;
else {
struct jobs_if *p;

for (p = jif_list; p != NULL; p = p->jif_next)
if (p->jif_next == jif) {
p->jif_next = jif->jif_next;
break;
}
ASSERT(p != NULL);
}
free(jif, M_DEVBUF);
}

/*
* bring the interface back to the initial state by discarding
* all the filters and classes.
*/
static int
jobs_clear_interface(struct jobs_if *jif)
{
struct jobs_class *cl;
int pri;

/* free the filters for this interface */
acc_discard_filters(&jif->jif_classifier, NULL, 1);

/* clear out the classes */
for (pri = 0; pri <= jif->jif_maxpri; pri++)
if ((cl = jif->jif_classes[pri]) != NULL)
jobs_class_destroy(cl);

return 0;
}

static int
jobs_request(struct ifaltq *ifq, int req, void *arg)
{
struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;

switch (req) {
case ALTRQ_PURGE:
jobs_purge(jif);
break;
}
return 0;
}

/* discard all the queued packets on the interface */
static void
jobs_purge(struct jobs_if *jif)
{
struct jobs_class *cl;
int pri;

for (pri = 0; pri <= jif->jif_maxpri; pri++) {
if ((cl = jif->jif_classes[pri]) != NULL && !qempty(cl->cl_q))
jobs_purgeq(cl);
}
if (ALTQ_IS_ENABLED(jif->jif_ifq))
jif->jif_ifq->ifq_len = 0;
}

static struct jobs_class *
jobs_class_create(struct jobs_if *jif, int pri, int64_t adc, int64_t rdc,
int64_t alc, int64_t rlc, int64_t arc, int flags)
{
struct jobs_class *cl, *scan1, *scan2;
int s;
int class_exists1, class_exists2;
int i, j;
int64_t tmp[JOBS_MAXPRI];
u_int64_t now;

if ((cl = jif->jif_classes[pri]) != NULL) {
/* modify the class instead of creating a new one */
s = splnet();
if (!qempty(cl->cl_q))
jobs_purgeq(cl);
splx(s);
} else {
cl = malloc(sizeof(struct jobs_class), M_DEVBUF,
M_WAITOK|M_ZERO);
if (cl == NULL)
return NULL;

cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF,
M_WAITOK|M_ZERO);
if (cl->cl_q == NULL)
goto err_ret;

cl->arv_tm = tslist_alloc();
if (cl->arv_tm == NULL)
goto err_ret;
}

jif->jif_classes[pri] = cl;

if (flags & JOCF_DEFAULTCLASS)
jif->jif_default = cl;

qtype(cl->cl_q) = Q_DROPTAIL;
qlen(cl->cl_q) = 0;
cl->service_rate = 0;
cl->min_rate_adc = 0;
cl->current_loss = 0;
cl->cl_period = 0;
PKTCNTR_RESET(&cl->cl_arrival);
PKTCNTR_RESET(&cl->cl_rin);
PKTCNTR_RESET(&cl->cl_rout);
PKTCNTR_RESET(&cl->cl_rout_th);
PKTCNTR_RESET(&cl->cl_dropcnt);
PKTCNTR_RESET(&cl->st_arrival);
PKTCNTR_RESET(&cl->st_rin);
PKTCNTR_RESET(&cl->st_rout);
PKTCNTR_RESET(&cl->st_dropcnt);
cl->st_service_rate = 0;
cl->cl_lastdel = 0;
cl->cl_avgdel = 0;
cl->adc_violations = 0;

if (adc == -1) {
cl->concerned_adc = 0;
adc = ALTQ_INFINITY;
} else
cl->concerned_adc = 1;

if (alc == -1) {
cl->concerned_alc = 0;
alc = ALTQ_INFINITY;
} else
cl->concerned_alc = 1;

if (rdc == -1) {
rdc = 0;
cl->concerned_rdc = 0;
} else
cl->concerned_rdc = 1;

if (rlc == -1) {
rlc = 0;
cl->concerned_rlc = 0;
} else
cl->concerned_rlc = 1;

if (arc == -1) {
arc = 0;
cl->concerned_arc = 0;
} else
cl->concerned_arc = 1;

cl->cl_rdc=rdc;

if (cl->concerned_adc) {
/* adc is given in us, convert it to clock ticks */
cl->cl_adc = (u_int64_t)(adc*machclk_freq/GRANULARITY);
} else
cl->cl_adc = adc;

if (cl->concerned_arc) {
/* arc is given in bps, convert it to internal unit */
cl->cl_arc = (u_int64_t)(bps_to_internal(arc));
} else
cl->cl_arc = arc;

cl->cl_rlc=rlc;
cl->cl_alc=alc;
cl->delay_prod_others = 0;
cl->loss_prod_others = 0;
cl->cl_flags = flags;
cl->cl_pri = pri;
if (pri > jif->jif_maxpri)
jif->jif_maxpri = pri;
cl->cl_jif = jif;
cl->cl_handle = (u_long)cl; /* just a pointer to this class */

/*
* update delay_prod_others and loss_prod_others
* in all classes if needed
*/

if (cl->concerned_rdc) {
for (i = 0; i <= jif->jif_maxpri; i++) {
scan1 = jif->jif_classes[i];
class_exists1 = (scan1 != NULL);
if (class_exists1) {
tmp[i] = 1;
for (j = 0; j <= i-1; j++) {
scan2 = jif->jif_classes[j];
class_exists2 = (scan2 != NULL);
if (class_exists2
&& scan2->concerned_rdc)
tmp[i] *= scan2->cl_rdc;
}
} else
tmp[i] = 0;
}

for (i = 0; i <= jif->jif_maxpri; i++) {
scan1 = jif->jif_classes[i];
class_exists1 = (scan1 != NULL);
if (class_exists1) {
scan1->delay_prod_others = 1;
for (j = 0; j <= jif->jif_maxpri; j++) {
scan2 = jif->jif_classes[j];
class_exists2 = (scan2 != NULL);
if (class_exists2 && j != i
&& scan2->concerned_rdc)
scan1->delay_prod_others *= tmp[j];
}
}
}
}

if (cl->concerned_rlc) {
for (i = 0; i <= jif->jif_maxpri; i++) {
scan1 = jif->jif_classes[i];
class_exists1 = (scan1 != NULL);
if (class_exists1) {
tmp[i] = 1;
for (j = 0; j <= i-1; j++) {
scan2 = jif->jif_classes[j];
class_exists2 = (scan2 != NULL);
if (class_exists2
&& scan2->concerned_rlc)
tmp[i] *= scan2->cl_rlc;
}
} else
tmp[i] = 0;
}

for (i = 0; i <= jif->jif_maxpri; i++) {
scan1 = jif->jif_classes[i];
class_exists1 = (scan1 != NULL);
if (class_exists1) {
scan1->loss_prod_others = 1;
for (j = 0; j <= jif->jif_maxpri; j++) {
scan2 = jif->jif_classes[j];
class_exists2 = (scan2 != NULL);
if (class_exists2 && j != i
&& scan2->concerned_rlc)
scan1->loss_prod_others *= tmp[j];
}
}
}
}

now = read_machclk();
cl->idletime = now;
return cl;

err_ret:
if (cl->cl_q != NULL)
free(cl->cl_q, M_DEVBUF);
if (cl->arv_tm != NULL)
free(cl->arv_tm, M_DEVBUF);

free(cl, M_DEVBUF);
return NULL;
}

static int
jobs_class_destroy(struct jobs_class *cl)
{
struct jobs_if *jif;
int s, pri;

s = splnet();

/* delete filters referencing to this class */
acc_discard_filters(&cl->cl_jif->jif_classifier, cl, 0);

if (!qempty(cl->cl_q))
jobs_purgeq(cl);

jif = cl->cl_jif;
jif->jif_classes[cl->cl_pri] = NULL;
if (jif->jif_maxpri == cl->cl_pri) {
for (pri = cl->cl_pri; pri >= 0; pri--)
if (jif->jif_classes[pri] != NULL) {
jif->jif_maxpri = pri;
break;
}
if (pri < 0)
jif->jif_maxpri = -1;
}
splx(s);

tslist_destroy(cl);
free(cl->cl_q, M_DEVBUF);
free(cl, M_DEVBUF);
return 0;
}

/*
* jobs_enqueue is an enqueue function to be registered to
* (*altq_enqueue) in struct ifaltq.
*/
static int
jobs_enqueue(struct ifaltq *ifq, struct mbuf *m)
{
struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;
struct jobs_class *cl, *scan;
int len;
int return_flag;
int pri;
u_int64_t now;
u_int64_t old_arv;
int64_t* delta_rate;
u_int64_t tstamp1, tstamp2, cycles; /* used for benchmarking only */

jif->total_enqueued++;
now = read_machclk();
tstamp1 = now;

return_flag = 0;

/* proceed with packet enqueuing */

if (IFQ_IS_EMPTY(ifq)) {
for (pri=0; pri <= jif->jif_maxpri; pri++) {
scan = jif->jif_classes[pri];
if (scan != NULL) {
/*
* reset all quantities, except:
* average delay, number of violations
*/
PKTCNTR_RESET(&scan->cl_rin);
PKTCNTR_RESET(&scan->cl_rout);
PKTCNTR_RESET(&scan->cl_rout_th);
PKTCNTR_RESET(&scan->cl_arrival);
PKTCNTR_RESET(&scan->cl_dropcnt);
scan->cl_lastdel = 0;
scan->current_loss = 0;
scan->service_rate = 0;
scan->idletime = now;
scan->cl_last_rate_update = now;
}
}
}

/* grab class set by classifier */
if ((cl = m->m_pkthdr.pattr_class) == NULL)
cl = jif->jif_default;

len = m_pktlen(m);
old_arv = cl->cl_arrival.bytes;
PKTCNTR_ADD(&cl->cl_arrival, (int)len);
PKTCNTR_ADD(&cl->cl_rin, (int)len);
PKTCNTR_ADD(&cl->st_arrival, (int)len);
PKTCNTR_ADD(&cl->st_rin, (int)len);

if (cl->cl_arrival.bytes < old_arv) {
/* deals w/ overflow */
for (pri=0; pri <= jif->jif_maxpri; pri++) {
scan = jif->jif_classes[pri];
if (scan != NULL) {
/*
* reset all quantities, except:
* average delay, number of violations
*/
PKTCNTR_RESET(&scan->cl_rin);
PKTCNTR_RESET(&scan->cl_rout);
PKTCNTR_RESET(&scan->cl_rout_th);
PKTCNTR_RESET(&scan->cl_arrival);
PKTCNTR_RESET(&scan->cl_dropcnt);
scan->current_loss = 0;
scan->service_rate = 0;
scan->idletime = now;
scan->cl_last_rate_update = now;
}
}
PKTCNTR_ADD(&cl->cl_arrival, (int)len);
PKTCNTR_ADD(&cl->cl_rin, (int)len);
}

if (cl->cl_arrival.bytes > cl->cl_rin.bytes)
cl->current_loss =
((cl->cl_arrival.bytes - cl->cl_rin.bytes) << SCALE_LOSS)
/ cl->cl_arrival.bytes;
else
cl->current_loss = 0;

/* for MDRR: update theoretical value of the output curve */

for (pri=0; pri <= jif->jif_maxpri; pri++) {
scan = jif->jif_classes[pri];
if (scan != NULL) {
if (scan->cl_last_rate_update == scan->idletime
|| scan->cl_last_rate_update == 0)
scan->cl_last_rate_update = now; /* initial case */
else
scan->cl_rout_th.bytes +=
delay_diff(now, scan->cl_last_rate_update)
* scan->service_rate;

/*
* we don't really care about packets here
* WARNING: rout_th is SCALED
* (b/c of the service rate)
* for precision, as opposed to rout.
*/

scan->cl_last_rate_update = now;
}
}

if (jobs_addq(cl, m, jif) != 0)
return_flag = ENOBUFS; /* signals there's a buffer overflow */
else
IFQ_INC_LEN(ifq);

/* successfully queued. */

enforce_wc(jif);

if (!min_rates_adc(jif)) {
delta_rate = assign_rate_drops_adc(jif);
if (delta_rate != NULL) {
for (pri = 0; pri <= jif->jif_maxpri; pri++)
if ((cl = jif->jif_classes[pri]) != NULL &&
!qempty(cl->cl_q))
cl->service_rate += delta_rate[pri];
free(delta_rate, M_DEVBUF);
}
}

delta_rate = adjust_rates_rdc(jif);

if (delta_rate != NULL) {
for (pri = 0; pri <= jif->jif_maxpri; pri++)
if ((cl = jif->jif_classes[pri]) != NULL &&
!qempty(cl->cl_q))
cl->service_rate += delta_rate[pri];
free(delta_rate, M_DEVBUF);
}

tstamp2 = read_machclk();
cycles = delay_diff(tstamp2, tstamp1);
if (cycles > jif->wc_cycles_enqueue)
jif->wc_cycles_enqueue=cycles;
if (cycles < jif->bc_cycles_enqueue)
jif->bc_cycles_enqueue=cycles;

jif->avg_cycles_enqueue += cycles;
jif->avg_cycles2_enqueue += cycles * cycles;

return return_flag;
}

/*
* jobs_dequeue is a dequeue function to be registered to
* (*altq_dequeue) in struct ifaltq.
*
* note: ALTDQ_POLL returns the next packet without removing the packet
* from the queue. ALTDQ_REMOVE is a normal dequeue operation.
* ALTDQ_REMOVE must return the same packet if called immediately
* after ALTDQ_POLL.
*/

static struct mbuf *
jobs_dequeue(struct ifaltq *ifq, int op)
{
struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;
struct jobs_class *cl;
struct mbuf *m;
int pri;
int svc_class;
int64_t max_error;
int64_t error;
u_int64_t now;
u_int64_t tstamp1, tstamp2, cycles;

jif->total_dequeued++;

now = read_machclk();
tstamp1 = now;

if (IFQ_IS_EMPTY(ifq)) {
/* no packet in the queue */
for (pri=0; pri <= jif->jif_maxpri; pri++) {
cl = jif->jif_classes[pri];
if (cl != NULL)
cl->idletime = now;
}

tstamp2 = read_machclk();
cycles = delay_diff(tstamp2, tstamp1);
if (cycles > jif->wc_cycles_dequeue)
jif->wc_cycles_dequeue = cycles;
if (cycles < jif->bc_cycles_dequeue)
jif->bc_cycles_dequeue = cycles;

jif->avg_cycles_dequeue += cycles;
jif->avg_cycles2_dequeue += cycles * cycles;

return NULL;
}

/*
* select the class whose actual tranmissions are the furthest
* from the promised transmissions
*/

max_error = -1;
svc_class = -1;

for (pri=0; pri <= jif->jif_maxpri; pri++) {
if (((cl = jif->jif_classes[pri]) != NULL)
&& !qempty(cl->cl_q)) {
error = (int64_t)cl->cl_rout_th.bytes
-(int64_t)scale_rate(cl->cl_rout.bytes);
if (max_error == -1) {
max_error = error;
svc_class = pri;
} else if (error > max_error) {
max_error = error;
svc_class = pri;
}
}
}

if (svc_class != -1)
cl = jif->jif_classes[svc_class];
else
cl = NULL;

if (op == ALTDQ_POLL) {
tstamp2 = read_machclk();
cycles = delay_diff(tstamp2, tstamp1);
if (cycles > jif->wc_cycles_dequeue)
jif->wc_cycles_dequeue = cycles;
if (cycles < jif->bc_cycles_dequeue)
jif->bc_cycles_dequeue = cycles;

jif->avg_cycles_dequeue += cycles;
jif->avg_cycles2_dequeue += cycles * cycles;

return (jobs_pollq(cl));
}

if (cl != NULL)
m = jobs_getq(cl);
else
m = NULL;

if (m != NULL) {
IFQ_DEC_LEN(ifq);
if (qempty(cl->cl_q))
cl->cl_period++;

cl->cl_lastdel = (u_int64_t)delay_diff(now,
tslist_first(cl->arv_tm)->timestamp);
if (cl->concerned_adc
&& (int64_t)cl->cl_lastdel > cl->cl_adc)
cl->adc_violations++;
cl->cl_avgdel += ticks_to_secs(GRANULARITY*cl->cl_lastdel);

PKTCNTR_ADD(&cl->cl_rout, m_pktlen(m));
PKTCNTR_ADD(&cl->st_rout, m_pktlen(m));
}
if (cl != NULL)
tslist_dequeue(cl); /* dequeue the timestamp */

tstamp2 = read_machclk();
cycles = delay_diff(tstamp2, tstamp1);
if (cycles > jif->wc_cycles_dequeue)
jif->wc_cycles_dequeue = cycles;
if (cycles < jif->bc_cycles_dequeue)
jif->bc_cycles_dequeue = cycles;

jif->avg_cycles_dequeue += cycles;
jif->avg_cycles2_dequeue += cycles * cycles;

return m;
}

static int
jobs_addq(struct jobs_class *cl, struct mbuf *m, struct jobs_if *jif)
{
int victim;
u_int64_t len;
u_int64_t now;
struct jobs_class* victim_class;

victim = -1;
victim_class = NULL;
len = 0;

now = read_machclk();

if (jif->jif_separate && qlen(cl->cl_q) >= jif->jif_qlimit) {
/*
* separate buffers: no guarantees on packet drops
* can be offered
* thus we drop the incoming packet
*/
len = (u_int64_t)m_pktlen(m);
PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
PKTCNTR_SUB(&cl->cl_rin, (int)len);
PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
PKTCNTR_SUB(&cl->st_rin, (int)len);
cl->current_loss += (len << SCALE_LOSS)
/cl->cl_arrival.bytes;
m_freem(m);
return (-1);

} else if (!jif->jif_separate
&& jif->jif_ifq->ifq_len >= jif->jif_qlimit) {
/* shared buffer: supports guarantees on losses */
if (!cl->concerned_rlc) {
if (!cl->concerned_alc) {
/*
* no ALC, no RLC on this class:
* drop the incoming packet
*/
len = (u_int64_t)m_pktlen(m);
PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
PKTCNTR_SUB(&cl->cl_rin, (int)len);
PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
PKTCNTR_SUB(&cl->st_rin, (int)len);
cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
m_freem(m);
return (-1);
} else {
/*
* no RLC, but an ALC:
* drop the incoming packet if possible
*/
len = (u_int64_t)m_pktlen(m);
if (cl->current_loss + (len << SCALE_LOSS)
/ cl->cl_arrival.bytes <= cl->cl_alc) {
PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
PKTCNTR_SUB(&cl->cl_rin, (int)len);
PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
PKTCNTR_SUB(&cl->st_rin, (int)len);
cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
m_freem(m);
return (-1);
} else {
/*
* the ALC would be violated:
* pick another class
*/
_addq(cl->cl_q, m);
tslist_enqueue(cl, now);

victim = pick_dropped_rlc(jif);

if (victim == -1) {
/*
* something went wrong
* let us discard
* the incoming packet,
* regardless of what
* may happen...
*/
victim_class = cl;
} else
victim_class = jif->jif_classes[victim];

if (victim_class != NULL) {
/*
* test for safety
* purposes...
* it must be true
*/
m = _getq_tail(victim_class->cl_q);
len = (u_int64_t)m_pktlen(m);
PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
PKTCNTR_SUB(&victim_class->st_rin, (int)len);
victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
m_freem(m); /* the packet is trashed here */
tslist_drop(victim_class); /* and its timestamp as well */
}
return (-1);
}
}
} else {
/*
* RLC on that class:
* pick class according to RLCs
*/
_addq(cl->cl_q, m);
tslist_enqueue(cl, now);

victim = pick_dropped_rlc(jif);
if (victim == -1) {
/*
* something went wrong
* let us discard the incoming packet,
* regardless of what may happen...
*/
victim_class = cl;
} else
victim_class = jif->jif_classes[victim];

if (victim_class != NULL) {
/*
* test for safety purposes...
* it must be true
*/
m = _getq_tail(victim_class->cl_q);
len = (u_int64_t)m_pktlen(m);
PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
PKTCNTR_SUB(&victim_class->st_rin, (int)len);
victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
m_freem(m); /* the packet is trashed here */
tslist_drop(victim_class); /* and its timestamp as well */
}
return -1;
}
}
/* else: no drop */

_addq(cl->cl_q, m);
tslist_enqueue(cl, now);

return 0;
}

static struct mbuf *
jobs_getq(struct jobs_class *cl)
{
return _getq(cl->cl_q);
}

static struct mbuf *
jobs_pollq(struct jobs_class *cl)
{
return qhead(cl->cl_q);
}

static void
jobs_purgeq(struct jobs_class *cl)
{
struct mbuf *m;

if (qempty(cl->cl_q))
return;

while ((m = _getq(cl->cl_q)) != NULL) {
PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m));
PKTCNTR_ADD(&cl->st_dropcnt, m_pktlen(m));
m_freem(m);
tslist_drop(cl);
}
ASSERT(qlen(cl->cl_q) == 0);
}

/*
* timestamp list support routines
*
* this implementation has been revamped and
* now uses a TAILQ structure.
* timestamp list holds class timestamps
* there is one timestamp list per class.
*/
static TSLIST *
tslist_alloc(void)
{
TSLIST *list_init;

list_init = malloc(sizeof(TSLIST), M_DEVBUF, M_WAITOK);
TAILQ_INIT(list_init);
return list_init;
}

static void
tslist_destroy(struct jobs_class *cl)
{
while (tslist_first(cl->arv_tm) != NULL)
tslist_dequeue(cl);

free(cl->arv_tm, M_DEVBUF);
}

static int
tslist_enqueue(struct jobs_class *cl, u_int64_t arv)
{
TSENTRY *pushed;
pushed = malloc(sizeof(TSENTRY), M_DEVBUF, M_WAITOK);
if (pushed == NULL)
return 0;

pushed->timestamp = arv;
TAILQ_INSERT_TAIL(cl->arv_tm, pushed, ts_list);
return 1;
}

static void
tslist_dequeue(struct jobs_class *cl)
{
TSENTRY *popped;
popped = tslist_first(cl->arv_tm);
if (popped != NULL) {
TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
free(popped, M_DEVBUF);
}
return;
}

static void
tslist_drop(struct jobs_class *cl)
{
TSENTRY *popped;
popped = tslist_last(cl->arv_tm);
if (popped != NULL) {
TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
free(popped, M_DEVBUF);
}
return;
}

/*
* rate allocation support routines
*/
/*
* enforce_wc: enforce that backlogged classes have non-zero
* service rate, and that non-backlogged classes have zero
* service rate.
*/

static int
enforce_wc(struct jobs_if *jif)
{
struct jobs_class *cl;

int64_t active_classes;
int pri;
int is_backlogged, class_exists, updated;

updated = 0;
active_classes = 0;

for (pri = 0; pri <= jif->jif_maxpri; pri++) {
cl = jif->jif_classes[pri];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged)
active_classes++;
if ((is_backlogged && cl->service_rate <= 0)
||(class_exists
&& !is_backlogged && cl->service_rate > 0))
updated = 1;
}

if (updated) {
for (pri = 0; pri <= jif->jif_maxpri; pri++) {
cl = jif->jif_classes[pri];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (class_exists && !is_backlogged)
cl->service_rate = 0;
else if (is_backlogged)
cl->service_rate = (int64_t)(bps_to_internal((u_int64_t)jif->jif_bandwidth)/active_classes);
}
}

return (updated);
}

/*
* adjust_rates_rdc: compute the service rates adjustments
* needed to realize the desired proportional delay differentiation.
* essentially, the rate adjustement delta_rate = prop_control*error,
* where error is the difference between the measured "weighted"
* delay and the mean of the weighted delays. see paper for more
* information.
* prop_control has slightly changed since the INFOCOM paper,
* this condition seems to provide better results.
*/

static int64_t *
adjust_rates_rdc(struct jobs_if *jif)
{
int64_t *result;
int64_t credit, available, lower_bound, upper_bound;
int64_t bk;
int i, j;
int rdc_classes, active_classes;
int class_exists, is_backlogged;
struct jobs_class *cl;
int64_t *error;
int64_t prop_control;
u_int64_t max_prod;
u_int64_t min_share;
u_int64_t max_avg_pkt_size;

/*
* min_share is scaled
* to avoid dealing with doubles
*/
active_classes = 0;
rdc_classes = 0;
max_prod = 0;
max_avg_pkt_size = 0;

upper_bound = (int64_t)jif->jif_bandwidth;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged) {
active_classes++;
if (cl->concerned_rdc)
rdc_classes++;
else
upper_bound -=
internal_to_bps(cl->service_rate);
}
}

result = malloc((jif->jif_maxpri+1)*sizeof(int64_t),
M_DEVBUF, M_WAITOK);

if (result == NULL)
return NULL;

for (i = 0; i <= jif->jif_maxpri; i++)
result[i] = 0;

if (upper_bound <= 0 || rdc_classes == 0)
return result;

credit = 0;
lower_bound = 0;
min_share = ((u_int64_t)1 << SCALE_SHARE);
bk = 0;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged && cl->concerned_rdc)
bk += cl->cl_rin.bytes;
}

if (bk == 0)
return result;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged
&& (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share)
min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk;
if (is_backlogged && cl->concerned_rdc
&& cl->delay_prod_others > max_prod)
max_prod = cl->delay_prod_others;

if (is_backlogged && cl->concerned_rdc
&& cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets)
max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets);
}

error = update_error(jif);
if (!error)
goto fail;

prop_control = (upper_bound*upper_bound*min_share)
/(max_prod*(max_avg_pkt_size << 2));

prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */

credit = 0;
for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged && cl->concerned_rdc) {
result[i] = -prop_control*error[i]; /* in BT-1 */
result[i] >>= (SCALE_SHARE);
}
}

free(error, M_DEVBUF); /* we don't need these anymore */

/* saturation */

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged && cl->concerned_rdc)
lower_bound += cl->min_rate_adc;
/*
* note: if there's no ADC or ARC on cl,
* this is equal to zero, which is fine
*/
}

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged && cl->concerned_rdc
&& result[i] + cl->service_rate > upper_bound) {
for (j = 0; j <= jif->jif_maxpri; j++) {
cl = jif->jif_classes[j];
class_exists = (cl != NULL);
is_backlogged = (class_exists
&& !qempty(cl->cl_q));
if (is_backlogged && cl->concerned_rdc) {
if (j == i)
result[j] = upper_bound
-cl->service_rate
+ cl->min_rate_adc
- lower_bound;
else
result[j] =
-cl->service_rate
+cl->min_rate_adc;
}
}
return result;
}

cl = jif->jif_classes[i];
/* do this again since it may have been modified */
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged && cl->concerned_rdc
&& result[i] + cl->service_rate < cl->min_rate_adc) {
credit += cl->service_rate+result[i]
-cl->min_rate_adc;
/* "credit" is in fact a negative number */
result[i] = -cl->service_rate+cl->min_rate_adc;
}
}

for (i = jif->jif_maxpri; (i >= 0 && credit < 0); i--) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged && cl->concerned_rdc) {
available = result[i]
+ cl->service_rate-cl->min_rate_adc;
if (available >= -credit) {
result[i] += credit;
credit = 0;
} else {
result[i] -= available;
credit += available;
}
}
}
return result;

fail: free(result, M_DEVBUF);
return NULL;
}

/*
* assign_rate_drops_adc: returns the adjustment needed to
* the service rates to meet the absolute delay/rate constraints
* (delay/throughput bounds) and drops traffic if need be.
* see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info.
*/

static int64_t *
assign_rate_drops_adc(struct jobs_if *jif)
{
int64_t *result;
int class_exists, is_backlogged;
struct jobs_class *cl;

int64_t *c, *n, *k;
int64_t *available;

int lowest, highest;
int keep_going;
int i;
u_int64_t now, oldest_arv;
int64_t remaining_time;
struct mbuf* pkt;
u_int64_t len;

now = read_machclk();
oldest_arv = now;

result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
if (result == NULL)
goto fail0;
c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
if (c == NULL)
goto fail1;
n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
if (n == NULL)
goto fail2;
k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
if (k == NULL)
goto fail3;
available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
if (available == NULL)
goto fail4;

for (i = 0; i <= jif->jif_maxpri; i++)
result[i] = 0;

keep_going = 1;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged) {
if (cl->concerned_adc) {
/*
* get the arrival time of the oldest
* class-i packet
*/
if (tslist_first(cl->arv_tm) == NULL)
oldest_arv = now; /* NOTREACHED */
else
oldest_arv = (tslist_first(cl->arv_tm))->timestamp;

n[i] = cl->service_rate;
k[i] = scale_rate((int64_t)(cl->cl_rin.bytes - cl->cl_rout.bytes));

remaining_time = cl->cl_adc
- (int64_t)delay_diff(now, oldest_arv);
if (remaining_time > 0) {
c[i] = remaining_time;
/*
* c is the remaining time before
* the deadline is violated
* (in ticks)
*/
available[i] = n[i]-k[i]/c[i];
} else {
/*
* deadline has passed...
* we allocate the whole link
* capacity to hopefully
* solve the problem
*/
c[i] = 0;
available[i] = -((int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth));
}
if (cl->concerned_arc) {
/*
* there's an ARC in addition
* to the ADC
*/
if (n[i] - cl->cl_arc < available[i])
available[i] = n[i]
- cl->cl_arc;
}
} else if (cl->concerned_arc) {
/*
* backlogged, concerned by ARC
* but not by ADC
*/
n[i] = cl->service_rate;
available[i] = n[i] - cl->cl_arc;
} else {
/*
* backlogged but not concerned by ADC
* or ARC -> can give everything
*/
n[i] = cl->service_rate;
available[i] = n[i];
}
} else {
/* not backlogged */
n[i] = 0;
k[i] = 0;
c[i] = 0;
if (class_exists)
available[i] = cl->service_rate;
else
available[i] = 0;
}
}

/* step 1: adjust rates (greedy algorithm) */

highest = 0;
lowest = jif->jif_maxpri;

while (highest < jif->jif_maxpri+1 && available[highest] >= 0)
highest++; /* which is the highest class that needs more service? */
while (lowest > 0 && available[lowest] <= 0)
lowest--; /* which is the lowest class that needs less service? */

while (highest != jif->jif_maxpri+1 && lowest != -1) {
/* give the excess service from lowest to highest */
if (available[lowest]+available[highest] > 0) {
/*
* still some "credit" left
* give all that is needed by "highest"
*/
n[lowest] += available[highest];
n[highest] -= available[highest];
available[lowest] += available[highest];
available[highest] = 0;

while (highest < jif->jif_maxpri+1
&& available[highest] >= 0)
highest++; /* which is the highest class that needs more service now? */

} else if (available[lowest]+available[highest] == 0) {
/* no more credit left but it's fine */
n[lowest] += available[highest];
n[highest] -= available[highest];
available[highest] = 0;
available[lowest] = 0;

while (highest < jif->jif_maxpri+1
&& available[highest] >= 0)
highest++; /* which is the highest class that needs more service? */
while (lowest >= 0 && available[lowest] <= 0)
lowest--; /* which is the lowest class that needs less service? */

} else if (available[lowest]+available[highest] < 0) {
/*
* no more credit left and we need to switch
* to another class
*/
n[lowest] -= available[lowest];
n[highest] += available[lowest];
available[highest] += available[lowest];
available[lowest] = 0;

while ((lowest >= 0)&&(available[lowest] <= 0))
lowest--; /* which is the lowest class that needs less service? */
}
}

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged) {
result[i] = n[i] - cl->service_rate;
} else {
if (class_exists)
result[i] = - cl->service_rate;
else
result[i] = 0;
}
}

/* step 2: adjust drops (for ADC) */

if (highest != jif->jif_maxpri+1) {
/* some class(es) still need(s) additional service */
for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists
&& !qempty(cl->cl_q));
if (is_backlogged && available[i] < 0) {
if (cl->concerned_adc) {
k[i] = c[i]*n[i];
while (keep_going && scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes)) > k[i]) {
pkt = qtail(cl->cl_q);
if (pkt != NULL) {
/* "safeguard" test (a packet SHOULD be in there) */
len = (u_int64_t)m_pktlen(pkt);
/* access packet at the tail */
if (cl->concerned_alc
&& cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
keep_going = 0; /* relax ADC in favor of ALC */
} else {
/* drop packet at the tail of the class-i queue, update values */
pkt = _getq_tail(cl->cl_q);
len = (u_int64_t)m_pktlen(pkt);
PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
PKTCNTR_SUB(&cl->cl_rin, (int)len);
PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
PKTCNTR_SUB(&cl->st_rin, (int)len);
cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
m_freem(pkt); /* the packet is trashed here */
tslist_drop(cl);
IFQ_DEC_LEN(cl->cl_jif->jif_ifq);
}
} else
keep_going = 0; /* NOTREACHED */
}
k[i] = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes));
}
/*
* n[i] is the max rate we can give.
* the above drops as much as possible
* to respect a delay bound.
* for throughput bounds,
* there's nothing that can be done
* after the greedy reallocation.
*/
}
}
}

/* update the values of min_rate_adc */
for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged && cl->concerned_adc) {
if (c[i] != 0) {
if (cl->concerned_adc
&& !cl->concerned_arc)
cl->min_rate_adc = k[i]/c[i];
else
cl->min_rate_adc = n[i];
} else
cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
} else if (is_backlogged && cl->concerned_arc)
cl->min_rate_adc = n[i]; /* the best we can give */
else {
if (class_exists)
cl->min_rate_adc = 0;
}
}

free(c, M_DEVBUF);
free(n, M_DEVBUF);
free(k, M_DEVBUF);
free(available, M_DEVBUF);

return result;

fail5: __unused
free(available, M_DEVBUF);
fail4: free(k, M_DEVBUF);
fail3: free(n, M_DEVBUF);
fail2: free(c, M_DEVBUF);
fail1: free(result, M_DEVBUF);
fail0: return NULL;
}

/*
* update_error: returns the difference between the mean weighted
* delay and the weighted delay for each class. if proportional
* delay differentiation is perfectly achieved, it should return
* zero for each class.
*/
static int64_t *
update_error(struct jobs_if *jif)
{
int i;
int active_classes;
u_int64_t mean_weighted_delay;
u_int64_t delays[JOBS_MAXPRI];
int64_t* error;
int class_exists, is_backlogged;
struct jobs_class *cl;

error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1), M_DEVBUF,
M_WAITOK|M_ZERO);

if (error == NULL)
return NULL;

mean_weighted_delay = 0;
active_classes = 0;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged) {
if (cl->concerned_rdc) {
delays[i] = proj_delay(jif, i);
mean_weighted_delay += cl->delay_prod_others*delays[i];
active_classes ++;
}
}
}

if (active_classes == 0)
return error;
else
mean_weighted_delay /= active_classes;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged && cl->concerned_rdc)
error[i] = ((int64_t)mean_weighted_delay)-((int64_t)cl->delay_prod_others*delays[i]);
else
error[i] = 0; /*
* either the class isn't concerned,
* or it's not backlogged.
* in any case, the rate shouldn't
* be adjusted.
*/
}
return error;
}

/*
* min_rates_adc: computes the minimum service rates needed in
* each class to meet the absolute delay bounds. if, for any
* class i, the current service rate of class i is less than
* the computed minimum service rate, this function returns
* false, true otherwise.
*/
static int
min_rates_adc(struct jobs_if *jif)
{
int result;
int i;
int class_exists, is_backlogged;
int64_t remaining_time;
struct jobs_class *cl;
result = 1;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged && cl->concerned_adc) {
remaining_time = cl->cl_adc - proj_delay(jif, i);
if (remaining_time > 0 ) {
/* min rate needed for ADC */
cl->min_rate_adc = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes))/remaining_time;
if (cl->concerned_arc
&& cl->cl_arc > cl->min_rate_adc) {
/* min rate needed for ADC + ARC */
cl->min_rate_adc = cl->cl_arc;
}
} else {
/* the deadline has been exceeded: give the whole link capacity to hopefully fix the situation */
cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
}
} else if (is_backlogged && cl->concerned_arc)
cl->min_rate_adc = cl->cl_arc; /* no ADC, an ARC */
else if (class_exists)
cl->min_rate_adc = 0; /*
* either the class is not
* backlogged
* or there is no ADC and
* no ARC
*/
if (is_backlogged && cl->min_rate_adc > cl->service_rate)
result = 0;
}

return result;
}

/*
* proj_delay: computes the difference between the current time
* and the time the oldest class-i packet still in the class-i
* queue i arrived in the system.
*/
static int64_t
proj_delay(struct jobs_if *jif, int i)
{
u_int64_t now;
int class_exists, is_backlogged;
struct jobs_class *cl;

now = read_machclk();
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));

if (is_backlogged)
return ((int64_t)delay_diff(now, tslist_first(cl->arv_tm)->timestamp));

return 0; /* NOTREACHED */
}

/*
* pick_dropped_rlc: returns the class index of the class to be
* dropped for meeting the relative loss constraints.
*/
static int
pick_dropped_rlc(struct jobs_if *jif)
{
int64_t mean;
int64_t* loss_error;
int i, active_classes;
int class_exists, is_backlogged;
int class_dropped;
int64_t max_error;
int64_t max_alc;
struct mbuf* pkt;
struct jobs_class *cl;
u_int64_t len;

loss_error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1),
M_DEVBUF, M_WAITOK);

if (loss_error == NULL)
return -1;

class_dropped = -1;
max_error = 0;
mean = 0;
active_classes = 0;

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists && !qempty(cl->cl_q));
if (is_backlogged) {
if (cl->concerned_rlc) {
mean += cl->loss_prod_others
* cl->current_loss;
active_classes++;
}
}
}

if (active_classes > 0)
mean /= active_classes;

if (active_classes == 0)
class_dropped = JOBS_MAXPRI+1; /*
* no classes are concerned
* by RLCs (JOBS_MAXPRI+1
* means "ignore RLC" here)
*/
else {
for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists
&& !qempty(cl->cl_q));

if ((is_backlogged)&&(cl->cl_rlc))
loss_error[i]=cl->loss_prod_others
*cl->current_loss-mean;
else
loss_error[i] = ALTQ_INFINITY;
}

for (i = 0; i <= jif->jif_maxpri; i++) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists
&& !qempty(cl->cl_q));
if (is_backlogged && loss_error[i] <= max_error) {
/*
* find out which class is the most
* below the mean.
* it's the one that needs to be dropped
* ties are broken in favor of the higher
* priority classes (i.e., if two classes
* present the same deviation, the lower
* priority class will get dropped).
*/
max_error = loss_error[i];
class_dropped = i;
}
}

if (class_dropped != -1) {
cl = jif->jif_classes[class_dropped];
pkt = qtail(cl->cl_q);
if (pkt != NULL) {
/*
* "safeguard" test (a packet SHOULD be
* in there)
*/
len = (u_int64_t)m_pktlen(pkt);
/* access packet at the tail */
if (cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
/*
* the class to drop for meeting
* the RLC will defeat the ALC:
* ignore RLC.
*/
class_dropped = JOBS_MAXPRI+1;
}
} else
class_dropped = JOBS_MAXPRI+1; /* NOTREACHED */
} else
class_dropped = JOBS_MAXPRI+1;
}

if (class_dropped == JOBS_MAXPRI+1) {
max_alc = -((int64_t)1 << SCALE_LOSS);
for (i = jif->jif_maxpri; i >= 0; i--) {
cl = jif->jif_classes[i];
class_exists = (cl != NULL);
is_backlogged = (class_exists
&& !qempty(cl->cl_q));
if (is_backlogged) {
if (cl->concerned_alc && cl->cl_alc - cl->current_loss > max_alc) {
max_alc = cl->cl_alc-cl->current_loss; /* pick the class which is the furthest from its ALC */
class_dropped = i;
} else if (!cl->concerned_alc && ((int64_t) 1 << SCALE_LOSS)-cl->current_loss > max_alc) {
max_alc = ((int64_t) 1 << SCALE_LOSS)-cl->current_loss;
class_dropped = i;
}
}
}
}

free(loss_error, M_DEVBUF);
return (class_dropped);
}

/*
* ALTQ binding/setup functions
*/
/*
* jobs device interface
*/
int
jobsopen(dev_t dev, int flag, int fmt,
struct lwp *l)
{
if (machclk_freq == 0)
init_machclk();

if (machclk_freq == 0) {
printf("jobs: no CPU clock available!\n");
return ENXIO;
}
/* everything will be done when the queueing scheme is attached. */
return 0;
}

int
jobsclose(dev_t dev, int flag, int fmt,
struct lwp *l)
{
struct jobs_if *jif;

while ((jif = jif_list) != NULL) {
/* destroy all */
if (ALTQ_IS_ENABLED(jif->jif_ifq))
altq_disable(jif->jif_ifq);

int error = altq_detach(jif->jif_ifq);
switch (error) {
case 0:
case ENXIO: /* already disabled */
break;
default:
return error;
}
jobs_detach(jif);
}

return 0;
}

int
jobsioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag,
struct lwp *l)
{
struct jobs_if *jif;
struct jobs_interface *ifacep;
int error = 0;

/* check super-user privilege */
switch (cmd) {
case JOBS_GETSTATS:
break;
default:
if ((error = kauth_authorize_network(l->l_cred,
KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_JOBS, NULL,
NULL, NULL)) != 0)
return (error);
break;
}

switch (cmd) {

case JOBS_IF_ATTACH:
error = jobscmd_if_attach((struct jobs_attach *)addr);
break;

case JOBS_IF_DETACH:
error = jobscmd_if_detach((struct jobs_interface *)addr);
break;

case JOBS_ENABLE:
case JOBS_DISABLE:
case JOBS_CLEAR:
ifacep = (struct jobs_interface *)addr;
if ((jif = altq_lookup(ifacep->jobs_ifname,
ALTQT_JOBS)) == NULL) {
error = EBADF;
break;
}

switch (cmd) {
case JOBS_ENABLE:
if (jif->jif_default == NULL) {
#if 1
printf("jobs: no default class\n");
#endif
error = EINVAL;
break;
}
error = altq_enable(jif->jif_ifq);
break;

case JOBS_DISABLE:
error = altq_disable(jif->jif_ifq);
break;

case JOBS_CLEAR:
jobs_clear_interface(jif);
break;
}
break;

case JOBS_ADD_CLASS:
error = jobscmd_add_class((struct jobs_add_class *)addr);
break;

case JOBS_DEL_CLASS:
error = jobscmd_delete_class((struct jobs_delete_class *)addr);
break;

case JOBS_MOD_CLASS:
error = jobscmd_modify_class((struct jobs_modify_class *)addr);
break;

case JOBS_ADD_FILTER:
error = jobscmd_add_filter((struct jobs_add_filter *)addr);
break;

case JOBS_DEL_FILTER:
error = jobscmd_delete_filter((struct jobs_delete_filter *)addr);
break;

case JOBS_GETSTATS:
error = jobscmd_class_stats((struct jobs_class_stats *)addr);
break;

default:
error = EINVAL;
break;
}
return error;
}

static int
jobscmd_if_attach(struct jobs_attach *ap)
{
struct jobs_if *jif;
struct ifnet *ifp;
int error;

if ((ifp = ifunit(ap->iface.jobs_ifname)) == NULL)
return ENXIO;
if ((jif = jobs_attach(&ifp->if_snd, ap->bandwidth, ap->qlimit, ap->separate)) == NULL)
return ENOMEM;

/*
* set JOBS to this ifnet structure.
*/
if ((error = altq_attach(&ifp->if_snd, ALTQT_JOBS, jif,
jobs_enqueue, jobs_dequeue, jobs_request,
&jif->jif_classifier, acc_classify)) != 0)
jobs_detach(jif);

return error;
}

static int
jobscmd_if_detach(struct jobs_interface *ap)
{
struct jobs_if *jif;
int error;

if ((jif = altq_lookup(ap->jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

if (ALTQ_IS_ENABLED(jif->jif_ifq))
altq_disable(jif->jif_ifq);

if ((error = altq_detach(jif->jif_ifq)))
return error;

jobs_detach(jif);
return 0;
}

static int
jobscmd_add_class(struct jobs_add_class *ap)
{
struct jobs_if *jif;
struct jobs_class *cl;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
return EINVAL;

if ((cl = jobs_class_create(jif, ap->pri,
ap->cl_adc, ap->cl_rdc,
ap->cl_alc, ap->cl_rlc, ap-> cl_arc,
ap->flags)) == NULL)
return ENOMEM;

/* return a class handle to the user */
ap->class_handle = clp_to_clh(cl);
return 0;
}

static int
jobscmd_delete_class(struct jobs_delete_class *ap)
{
struct jobs_if *jif;
struct jobs_class *cl;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
return EINVAL;

return jobs_class_destroy(cl);
}

static int
jobscmd_modify_class(struct jobs_modify_class *ap)
{
struct jobs_if *jif;
struct jobs_class *cl;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
return EINVAL;

if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
return EINVAL;

/*
* if priority is changed, move the class to the new priority
*/
if (jif->jif_classes[ap->pri] != cl) {
if (jif->jif_classes[ap->pri] != NULL)
return EEXIST;
jif->jif_classes[cl->cl_pri] = NULL;
jif->jif_classes[ap->pri] = cl;
cl->cl_pri = ap->pri;
}

/* call jobs_class_create to change class parameters */
if ((cl = jobs_class_create(jif, ap->pri,
ap->cl_adc, ap->cl_rdc,
ap->cl_alc, ap->cl_rlc, ap->cl_arc,
ap->flags)) == NULL)
return ENOMEM;
return 0;
}

static int
jobscmd_add_filter(struct jobs_add_filter *ap)
{
struct jobs_if *jif;
struct jobs_class *cl;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
return EINVAL;

return acc_add_filter(&jif->jif_classifier, &ap->filter,
cl, &ap->filter_handle);
}

static int
jobscmd_delete_filter(struct jobs_delete_filter *ap)
{
struct jobs_if *jif;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

return acc_delete_filter(&jif->jif_classifier, ap->filter_handle);
}

static int
jobscmd_class_stats(struct jobs_class_stats *ap)
{
struct jobs_if *jif;
struct jobs_class *cl;
struct class_stats stats, *usp;
int pri, error;

if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
return EBADF;

ap->maxpri = jif->jif_maxpri;

/* then, read the next N classes */
usp = ap->stats;
for (pri = 0; pri <= jif->jif_maxpri; pri++) {
cl = jif->jif_classes[pri];
(void)memset(&stats, 0, sizeof(stats));
if (cl != NULL)
get_class_stats(&stats, cl);
if ((error = copyout((void *)&stats, (void *)usp++,
sizeof(stats))) != 0)
return error;
}
return 0;
}

static void
get_class_stats(struct class_stats *sp, struct jobs_class *cl)
{
u_int64_t now;
now = read_machclk();

sp->class_handle = clp_to_clh(cl);
sp->qlength = qlen(cl->cl_q);

sp->period = cl->cl_period;
sp->rin = cl->st_rin;
sp->arrival = cl->st_arrival;
sp->arrivalbusy = cl->cl_arrival;
sp->rout = cl->st_rout;
sp->dropcnt = cl->cl_dropcnt;

/* PKTCNTR_RESET(&cl->st_arrival);*/
PKTCNTR_RESET(&cl->st_rin);
PKTCNTR_RESET(&cl->st_rout);

sp->totallength = cl->cl_jif->jif_ifq->ifq_len;
sp->lastdel = ticks_to_secs(GRANULARITY*cl->cl_lastdel);
sp->avgdel = cl->cl_avgdel;

cl->cl_avgdel = 0;

sp->busylength = ticks_to_secs(1000*delay_diff(now, cl->idletime));
sp->adc_violations = cl->adc_violations;

sp->wc_cycles_enqueue = cl->cl_jif->wc_cycles_enqueue;
sp->wc_cycles_dequeue = cl->cl_jif->wc_cycles_dequeue;
sp->bc_cycles_enqueue = cl->cl_jif->bc_cycles_enqueue;
sp->bc_cycles_dequeue = cl->cl_jif->bc_cycles_dequeue;
sp->avg_cycles_enqueue = cl->cl_jif->avg_cycles_enqueue;
sp->avg_cycles_dequeue = cl->cl_jif->avg_cycles_dequeue;
sp->avg_cycles2_enqueue = cl->cl_jif->avg_cycles2_enqueue;
sp->avg_cycles2_dequeue = cl->cl_jif->avg_cycles2_dequeue;
sp->total_enqueued = cl->cl_jif->total_enqueued;
sp->total_dequeued = cl->cl_jif->total_dequeued;
}

/* convert a class handle to the corresponding class pointer */
static struct jobs_class *
clh_to_clp(struct jobs_if *jif, u_long chandle)
{
struct jobs_class *cl;

cl = (struct jobs_class *)chandle;
if (chandle != ALIGN(cl)) {
#if 1
printf("clh_to_cl: unaligned pointer %p\n", cl);
#endif
return NULL;
}

if (cl == NULL || cl->cl_handle != chandle || cl->cl_jif != jif)
return NULL;
return cl;
}

/* convert a class pointer to the corresponding class handle */
static u_long
clp_to_clh(struct jobs_class *cl)
{
return (cl->cl_handle);
}

#ifdef KLD_MODULE

static struct altqsw jobs_sw =
{"jobs", jobsopen, jobsclose, jobsioctl};

ALTQ_MODULE(altq_jobs, ALTQT_JOBS, &jobs_sw);

#endif /* KLD_MODULE */

#endif /* ALTQ3_COMPAT */
#endif /* ALTQ_JOBS */