pktsched_rmclass.c [plain text]
#include <sys/cdefs.h>
#ident "@(#)rm_class.c 1.48 97/12/05 SMI"
#if PKTSCHED_CBQ
#include <sys/param.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/socket.h>
#include <sys/systm.h>
#include <sys/errno.h>
#include <sys/time.h>
#include <sys/kernel.h>
#include <sys/kernel_types.h>
#include <sys/syslog.h>
#include <kern/zalloc.h>
#include <net/if.h>
#include <net/net_osdep.h>
#include <net/pktsched/pktsched.h>
#include <net/pktsched/pktsched_rmclass.h>
#include <net/pktsched/pktsched_rmclass_debug.h>
#include <net/classq/classq_red.h>
#include <net/classq/classq_rio.h>
#include <net/classq/classq_blue.h>
#include <net/classq/classq_sfb.h>
#define reset_cutoff(ifd) { ifd->cutoff_ = RM_MAXDEPTH; }
static int rmc_satisfied(struct rm_class *, struct timeval *);
static void rmc_wrr_set_weights(struct rm_ifdat *);
static void rmc_depth_compute(struct rm_class *);
static void rmc_depth_recompute(rm_class_t *);
static struct mbuf *_rmc_wrr_dequeue_next(struct rm_ifdat *, cqdq_op_t);
static struct mbuf *_rmc_prr_dequeue_next(struct rm_ifdat *, cqdq_op_t);
static int _rmc_addq(rm_class_t *, struct mbuf *, struct pf_mtag *);
static void _rmc_dropq(rm_class_t *);
static struct mbuf *_rmc_getq(rm_class_t *);
static struct mbuf *_rmc_pollq(rm_class_t *);
static int rmc_under_limit(struct rm_class *, struct timeval *);
static void rmc_tl_satisfied(struct rm_ifdat *, struct timeval *);
static void rmc_drop_action(struct rm_class *);
static void rmc_restart(struct rm_class *);
static void rmc_root_overlimit(rm_class_t *, rm_class_t *);
#define RMC_ZONE_MAX 32
#define RMC_ZONE_NAME "pktsched_cbq_cl"
static unsigned int rmc_size;
static struct zone *rmc_zone;
void
rmclass_init(void)
{
if (rmc_zone != NULL)
return;
rmc_size = sizeof (struct rm_class);
rmc_zone = zinit(rmc_size, RMC_ZONE_MAX * rmc_size, 0, RMC_ZONE_NAME);
if (rmc_zone == NULL) {
panic("%s: failed allocating %s", __func__, RMC_ZONE_NAME);
}
zone_change(rmc_zone, Z_EXPAND, TRUE);
zone_change(rmc_zone, Z_CALLERACCT, TRUE);
}
#define BORROW_OFFTIME
#define ADJUST_CUTOFF
struct rm_class *
rmc_newclass(int pri, struct rm_ifdat *ifd, u_int32_t nsecPerByte,
void (*action)(rm_class_t *, rm_class_t *), u_int32_t qid, u_int32_t maxq,
struct rm_class *parent, struct rm_class *borrow, u_int32_t maxidle,
int minidle, u_int32_t offtime, int pktsize, int flags)
{
struct ifnet *ifp;
struct ifclassq *ifq;
struct rm_class *cl;
struct rm_class *peer;
if (nsecPerByte == 0) {
log(LOG_ERR, "%s: invalid inverse data rate\n", __func__);
return (NULL);
}
if (pri >= RM_MAXPRIO) {
log(LOG_ERR, "%s: priority %d out of range! (max %d)\n",
__func__, pri, RM_MAXPRIO - 1);
return (NULL);
}
#if !CLASSQ_RED
if (flags & RMCF_RED) {
log(LOG_ERR, "%s: RED not configured for CBQ!\n", __func__);
return (NULL);
}
#endif
#if !CLASSQ_RIO
if (flags & RMCF_RIO) {
log(LOG_ERR, "%s: RIO not configured for CBQ!\n", __func__);
return (NULL);
}
#endif
#if !CLASSQ_BLUE
if (flags & RMCF_BLUE) {
log(LOG_ERR, "%s: BLUE not configured for CBQ!\n", __func__);
return (NULL);
}
#endif
if ((flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) &&
(flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) != RMCF_RED &&
(flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) != RMCF_RIO &&
(flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) != RMCF_BLUE &&
(flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) != RMCF_SFB) {
log(LOG_ERR, "%s: RED|RIO|BLUE|SFB mutually exclusive\n",
__func__);
return (NULL);
}
cl = zalloc(rmc_zone);
if (cl == NULL)
return (NULL);
bzero(cl, rmc_size);
CALLOUT_INIT(&cl->callout_);
cl->children_ = NULL;
cl->parent_ = parent;
cl->borrow_ = borrow;
cl->leaf_ = 1;
cl->ifdat_ = ifd;
cl->pri_ = pri;
cl->allotment_ = RM_NS_PER_SEC / nsecPerByte;
cl->depth_ = 0;
cl->qthresh_ = 0;
cl->ns_per_byte_ = nsecPerByte;
ifq = ifd->ifq_;
ifp = ifq->ifcq_ifp;
if (maxq == 0 || maxq > IFCQ_MAXLEN(ifq)) {
maxq = IFCQ_MAXLEN(ifq);
if (maxq == 0)
maxq = DEFAULT_QLIMIT;
}
_qinit(&cl->q_, Q_DROPHEAD, maxq);
cl->flags_ = flags;
cl->minidle_ = (minidle * (int)nsecPerByte) / 8;
if (cl->minidle_ > 0)
cl->minidle_ = 0;
cl->maxidle_ = (maxidle * nsecPerByte) / 8;
if (cl->maxidle_ == 0)
cl->maxidle_ = 1;
cl->avgidle_ = cl->maxidle_;
cl->offtime_ = ((offtime * nsecPerByte) / 8) >> RM_FILTER_GAIN;
if (cl->offtime_ == 0)
cl->offtime_ = 1;
cl->overlimit = action;
if (flags & (RMCF_RED|RMCF_RIO|RMCF_BLUE|RMCF_SFB)) {
int pkttime;
cl->qflags_ = 0;
if (flags & RMCF_ECN) {
if (flags & RMCF_BLUE)
cl->qflags_ |= BLUEF_ECN;
else if (flags & RMCF_SFB)
cl->qflags_ |= SFBF_ECN;
else if (flags & RMCF_RED)
cl->qflags_ |= REDF_ECN;
else if (flags & RMCF_RIO)
cl->qflags_ |= RIOF_ECN;
}
if (flags & RMCF_FLOWCTL) {
if (flags & RMCF_SFB)
cl->qflags_ |= SFBF_FLOWCTL;
}
if (flags & RMCF_FLOWVALVE) {
if (flags & RMCF_RED)
cl->qflags_ |= REDF_FLOWVALVE;
}
if (flags & RMCF_CLEARDSCP) {
if (flags & RMCF_RIO)
cl->qflags_ |= RIOF_CLEARDSCP;
}
pkttime = nsecPerByte * pktsize / 1000;
#if CLASSQ_RED
if (flags & RMCF_RED) {
cl->red_ = red_alloc(ifp, 0, 0,
qlimit(&cl->q_) * 10/100,
qlimit(&cl->q_) * 30/100,
cl->qflags_, pkttime);
if (cl->red_ != NULL)
qtype(&cl->q_) = Q_RED;
}
#endif
#if CLASSQ_RIO
if (flags & RMCF_RIO) {
cl->rio_ =
rio_alloc(ifp, 0, NULL, cl->qflags_, pkttime);
if (cl->rio_ != NULL)
qtype(&cl->q_) = Q_RIO;
}
#endif
#if CLASSQ_BLUE
if (flags & RMCF_BLUE) {
cl->blue_ = blue_alloc(ifp, 0, 0, cl->qflags_);
if (cl->blue_ != NULL)
qtype(&cl->q_) = Q_BLUE;
}
#endif
if (flags & RMCF_SFB) {
if (!(cl->flags_ & RMCF_LAZY))
cl->sfb_ = sfb_alloc(ifp, qid,
qlimit(&cl->q_), cl->qflags_);
if (cl->sfb_ != NULL || (cl->flags_ & RMCF_LAZY))
qtype(&cl->q_) = Q_SFB;
}
}
if ((peer = ifd->active_[pri]) != NULL) {
cl->peer_ = peer;
while (peer->peer_ != ifd->active_[pri])
peer = peer->peer_;
peer->peer_ = cl;
} else {
ifd->active_[pri] = cl;
cl->peer_ = cl;
}
if (cl->parent_) {
cl->next_ = parent->children_;
parent->children_ = cl;
parent->leaf_ = 0;
}
rmc_depth_compute(cl);
if (ifd->wrr_) {
ifd->num_[pri]++;
ifd->alloc_[pri] += cl->allotment_;
rmc_wrr_set_weights(ifd);
}
return (cl);
}
int
rmc_modclass(struct rm_class *cl, u_int32_t nsecPerByte, int maxq,
u_int32_t maxidle, int minidle, u_int32_t offtime, int pktsize)
{
#pragma unused(pktsize)
struct rm_ifdat *ifd;
u_int32_t old_allotment;
ifd = cl->ifdat_;
old_allotment = cl->allotment_;
cl->allotment_ = RM_NS_PER_SEC / nsecPerByte;
cl->qthresh_ = 0;
cl->ns_per_byte_ = nsecPerByte;
qlimit(&cl->q_) = maxq;
cl->minidle_ = (minidle * nsecPerByte) / 8;
if (cl->minidle_ > 0)
cl->minidle_ = 0;
cl->maxidle_ = (maxidle * nsecPerByte) / 8;
if (cl->maxidle_ == 0)
cl->maxidle_ = 1;
cl->avgidle_ = cl->maxidle_;
cl->offtime_ = ((offtime * nsecPerByte) / 8) >> RM_FILTER_GAIN;
if (cl->offtime_ == 0)
cl->offtime_ = 1;
if (ifd->wrr_) {
ifd->alloc_[cl->pri_] += cl->allotment_ - old_allotment;
rmc_wrr_set_weights(ifd);
}
return (0);
}
static void
rmc_wrr_set_weights(struct rm_ifdat *ifd)
{
int i;
struct rm_class *cl, *clh;
for (i = 0; i < RM_MAXPRIO; i++) {
if (ifd->num_[i] == 0) {
ifd->M_[i] = 0;
} else {
ifd->M_[i] =
ifd->alloc_[i] / (ifd->num_[i] * ifd->maxpkt_);
}
if (ifd->active_[i] != NULL) {
clh = cl = ifd->active_[i];
do {
if (ifd->M_[i] == 0) {
cl->w_allotment_ = 0;
} else {
cl->w_allotment_ =
cl->allotment_ / ifd->M_[i];
}
cl = cl->peer_;
} while ((cl != NULL) && (cl != clh));
}
}
}
int
rmc_get_weight(struct rm_ifdat *ifd, int pri)
{
if ((pri >= 0) && (pri < RM_MAXPRIO))
return (ifd->M_[pri]);
else
return (0);
}
static void
rmc_depth_compute(struct rm_class *cl)
{
rm_class_t *t = cl, *p;
while (t != NULL) {
p = t->parent_;
if (p && (t->depth_ >= p->depth_)) {
p->depth_ = t->depth_ + 1;
t = p;
} else
t = NULL;
}
}
static void
rmc_depth_recompute(rm_class_t *cl)
{
rm_class_t *p, *t;
p = cl;
while (p != NULL) {
if ((t = p->children_) == NULL) {
p->depth_ = 0;
} else {
int cdepth = 0;
while (t != NULL) {
if (t->depth_ > cdepth)
cdepth = t->depth_;
t = t->next_;
}
if (p->depth_ == cdepth + 1)
return;
p->depth_ = cdepth + 1;
}
p = p->parent_;
}
}
void
rmc_delete_class(struct rm_ifdat *ifd, struct rm_class *cl)
{
struct rm_class *p, *head, *previous;
VERIFY(cl->children_ == NULL);
if (cl->sleeping_)
CALLOUT_STOP(&cl->callout_);
rmc_dropall(cl);
if (cl->parent_ != NULL) {
head = cl->parent_->children_;
p = previous = head;
if (head->next_ == NULL) {
VERIFY(head == cl);
cl->parent_->children_ = NULL;
cl->parent_->leaf_ = 1;
} else while (p != NULL) {
if (p == cl) {
if (cl == head)
cl->parent_->children_ = cl->next_;
else
previous->next_ = cl->next_;
cl->next_ = NULL;
p = NULL;
} else {
previous = p;
p = p->next_;
}
}
}
if ((p = ifd->active_[cl->pri_]) != NULL) {
if (p != p->peer_) {
while (p->peer_ != cl)
p = p->peer_;
p->peer_ = cl->peer_;
if (ifd->active_[cl->pri_] == cl)
ifd->active_[cl->pri_] = cl->peer_;
} else {
VERIFY(p == cl);
ifd->active_[cl->pri_] = NULL;
}
}
if (ifd->wrr_) {
ifd->alloc_[cl->pri_] -= cl->allotment_;
ifd->num_[cl->pri_]--;
rmc_wrr_set_weights(ifd);
}
rmc_depth_recompute(cl->parent_);
if (cl->qalg_.ptr != NULL) {
#if CLASSQ_RIO
if (q_is_rio(&cl->q_))
rio_destroy(cl->rio_);
#endif
#if CLASSQ_RED
if (q_is_red(&cl->q_))
red_destroy(cl->red_);
#endif
#if CLASSQ_BLUE
if (q_is_blue(&cl->q_))
blue_destroy(cl->blue_);
#endif
if (q_is_sfb(&cl->q_) && cl->sfb_ != NULL)
sfb_destroy(cl->sfb_);
cl->qalg_.ptr = NULL;
qtype(&cl->q_) = Q_DROPTAIL;
qstate(&cl->q_) = QS_RUNNING;
}
zfree(rmc_zone, cl);
}
int
rmc_init(struct ifclassq *ifq, struct rm_ifdat *ifd, u_int32_t nsecPerByte,
void (*restart)(struct ifclassq *), u_int32_t qid, int maxq, int maxqueued,
u_int32_t maxidle, int minidle, u_int32_t offtime, int flags)
{
struct ifnet *ifp = ifq->ifcq_ifp;
int i, mtu;
CBQTRACEINIT();
if (nsecPerByte == 0) {
log(LOG_ERR, "%s: %s: invalid inverse data rate)\n",
__func__, if_name(ifp));
return (EINVAL);
}
mtu = ifp->if_mtu;
if (mtu < 1) {
log(LOG_ERR, "%s: %s: invalid MTU (interface not "
"initialized?)\n", __func__, if_name(ifp));
return (EINVAL);
}
bzero((char *)ifd, sizeof (*ifd));
ifd->ifq_ = ifq;
ifd->restart = restart;
ifd->maxqueued_ = maxqueued;
ifd->ns_per_byte_ = nsecPerByte;
ifd->maxpkt_ = mtu;
ifd->wrr_ = (flags & RMCF_WRR) ? 1 : 0;
ifd->efficient_ = (flags & RMCF_EFFICIENT) ? 1 : 0;
#if 1
ifd->maxiftime_ = mtu * nsecPerByte / 1000 * 16;
if (mtu * nsecPerByte > 10 * 1000000)
ifd->maxiftime_ /= 4;
#endif
reset_cutoff(ifd);
CBQTRACE(rmc_init, 'INIT', ifd->cutoff_);
for (i = 0; i < RM_MAXPRIO; i++) {
ifd->alloc_[i] = 0;
ifd->M_[i] = 0;
ifd->num_[i] = 0;
ifd->na_[i] = 0;
ifd->active_[i] = NULL;
}
ifd->qi_ = 0;
ifd->qo_ = 0;
for (i = 0; i < RM_MAXQUEUED; i++) {
ifd->class_[i] = NULL;
ifd->curlen_[i] = 0;
ifd->borrowed_[i] = NULL;
}
if ((ifd->root_ = rmc_newclass(0, ifd, nsecPerByte,
rmc_root_overlimit, qid, maxq, 0, 0, maxidle, minidle, offtime,
0, 0)) == NULL) {
log(LOG_ERR, "rmc_init: root class not allocated\n");
return (ENOMEM);
}
ifd->root_->depth_ = 0;
return (0);
}
int
rmc_queue_packet(struct rm_class *cl, struct mbuf *m, struct pf_mtag *t)
{
struct timeval now;
struct rm_ifdat *ifd = cl->ifdat_;
int cpri = cl->pri_;
int is_empty = qempty(&cl->q_);
int ret = 0;
RM_GETTIME(now);
if (ifd->cutoff_ > 0) {
if (TV_LT(&cl->undertime_, &now)) {
if (ifd->cutoff_ > cl->depth_)
ifd->cutoff_ = cl->depth_;
CBQTRACE(rmc_queue_packet, 'ffoc', cl->depth_);
} else {
struct rm_class *borrow = cl->borrow_;
while (borrow != NULL &&
borrow->depth_ < ifd->cutoff_) {
if (TV_LT(&borrow->undertime_, &now)) {
ifd->cutoff_ = borrow->depth_;
CBQTRACE(rmc_queue_packet, 'ffob',
ifd->cutoff_);
break;
}
borrow = borrow->borrow_;
}
}
}
ret = _rmc_addq(cl, m, t);
if (ret != 0 &&
(ret == CLASSQEQ_DROPPED || ret == CLASSQEQ_DROPPED_FC ||
ret == CLASSQEQ_DROPPED_SP)) {
return (ret);
}
VERIFY(ret == 0 || ret == CLASSQEQ_SUCCESS_FC);
if (is_empty) {
CBQTRACE(rmc_queue_packet, 'type', cl->stats_.handle);
ifd->na_[cpri]++;
}
if (qlen(&cl->q_) > qlimit(&cl->q_)) {
rmc_drop_action(cl);
return (CLASSQEQ_DROPPED);
}
return (ret);
}
static void
rmc_tl_satisfied(struct rm_ifdat *ifd, struct timeval *now)
{
int i;
rm_class_t *p, *bp;
for (i = RM_MAXPRIO - 1; i >= 0; i--) {
if ((bp = ifd->active_[i]) != NULL) {
p = bp;
do {
if (!rmc_satisfied(p, now)) {
ifd->cutoff_ = p->depth_;
return;
}
p = p->peer_;
} while (p != bp);
}
}
reset_cutoff(ifd);
}
static int
rmc_satisfied(struct rm_class *cl, struct timeval *now)
{
rm_class_t *p;
if (cl == NULL)
return (1);
if (TV_LT(now, &cl->undertime_))
return (1);
if (cl->depth_ == 0) {
if (!cl->sleeping_ && (qlen(&cl->q_) > cl->qthresh_))
return (0);
else
return (1);
}
if (cl->children_ != NULL) {
p = cl->children_;
while (p != NULL) {
if (!rmc_satisfied(p, now))
return (0);
p = p->next_;
}
}
return (1);
}
static int
rmc_under_limit(struct rm_class *cl, struct timeval *now)
{
rm_class_t *p = cl;
rm_class_t *top;
struct rm_ifdat *ifd = cl->ifdat_;
ifd->borrowed_[ifd->qi_] = NULL;
if (cl->parent_ == NULL)
return (1);
if (cl->sleeping_) {
if (TV_LT(now, &cl->undertime_))
return (0);
CALLOUT_STOP(&cl->callout_);
cl->sleeping_ = 0;
cl->undertime_.tv_sec = 0;
return (1);
}
top = NULL;
while (cl->undertime_.tv_sec && TV_LT(now, &cl->undertime_)) {
if (((cl = cl->borrow_) == NULL) ||
(cl->depth_ > ifd->cutoff_)) {
#ifdef ADJUST_CUTOFF
if (cl != NULL)
return (0);
#endif
#ifdef BORROW_OFFTIME
if (cl != NULL) {
top = cl;
CBQTRACE(rmc_under_limit, 'ffou', ifd->cutoff_);
}
if (top != NULL && top->avgidle_ == top->minidle_)
top = NULL;
p->overtime_ = *now;
(p->overlimit)(p, top);
#else
p->overtime_ = *now;
(p->overlimit)(p, NULL);
#endif
return (0);
}
top = cl;
}
if (cl != p)
ifd->borrowed_[ifd->qi_] = cl;
return (1);
}
static struct mbuf *
_rmc_wrr_dequeue_next(struct rm_ifdat *ifd, cqdq_op_t op)
{
struct rm_class *cl = NULL, *first = NULL;
u_int32_t deficit;
int cpri;
struct mbuf *m;
struct timeval now;
RM_GETTIME(now);
if (op == CLASSQDQ_REMOVE && ifd->pollcache_) {
cl = ifd->pollcache_;
cpri = cl->pri_;
if (ifd->efficient_) {
if (cl->undertime_.tv_sec != 0 &&
rmc_under_limit(cl, &now) == 0)
first = cl;
}
ifd->pollcache_ = NULL;
goto _wrr_out;
} else {
ifd->pollcache_ = NULL;
ifd->borrowed_[ifd->qi_] = NULL;
}
#ifdef ADJUST_CUTOFF
_again:
#endif
for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) {
if (ifd->na_[cpri] == 0)
continue;
deficit = 0;
_wrr_loop:
cl = ifd->active_[cpri];
VERIFY(cl != NULL);
do {
if ((deficit < 2) && (cl->bytes_alloc_ <= 0))
cl->bytes_alloc_ += cl->w_allotment_;
if (!qempty(&cl->q_)) {
if ((cl->undertime_.tv_sec == 0) ||
rmc_under_limit(cl, &now)) {
if (cl->bytes_alloc_ > 0 || deficit > 1)
goto _wrr_out;
deficit = 1;
#if 1
ifd->borrowed_[ifd->qi_] = NULL;
#endif
} else if (first == NULL && cl->borrow_ != NULL)
first = cl;
}
cl->bytes_alloc_ = 0;
cl = cl->peer_;
} while (cl != ifd->active_[cpri]);
if (deficit == 1) {
deficit = 2;
goto _wrr_loop;
}
}
#ifdef ADJUST_CUTOFF
if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) {
ifd->cutoff_++;
CBQTRACE(_rmc_wrr_dequeue_next, 'ojda', ifd->cutoff_);
goto _again;
}
#endif
reset_cutoff(ifd);
CBQTRACE(_rmc_wrr_dequeue_next, 'otsr', ifd->cutoff_);
if (!ifd->efficient_ || first == NULL)
return (NULL);
cl = first;
cpri = cl->pri_;
#if 0
if (cl->sleeping_)
CALLOUT_STOP(&cl->callout_);
cl->sleeping_ = 0;
cl->undertime_.tv_sec = 0;
#endif
ifd->borrowed_[ifd->qi_] = cl->borrow_;
ifd->cutoff_ = cl->borrow_->depth_;
_wrr_out:
if (op == CLASSQDQ_REMOVE) {
m = _rmc_getq(cl);
if (m == NULL)
return (NULL);
if (qempty(&cl->q_))
ifd->na_[cpri]--;
if (cl->bytes_alloc_ > 0)
cl->bytes_alloc_ -= m_pktlen(m);
if ((cl->bytes_alloc_ <= 0) || first == cl)
ifd->active_[cl->pri_] = cl->peer_;
else
ifd->active_[cl->pri_] = cl;
ifd->class_[ifd->qi_] = cl;
ifd->curlen_[ifd->qi_] = m_pktlen(m);
ifd->now_[ifd->qi_] = now;
ifd->qi_ = (ifd->qi_ + 1) % ifd->maxqueued_;
ifd->queued_++;
} else {
m = _rmc_pollq(cl);
ifd->pollcache_ = cl;
}
return (m);
}
static struct mbuf *
_rmc_prr_dequeue_next(struct rm_ifdat *ifd, cqdq_op_t op)
{
struct mbuf *m;
int cpri;
struct rm_class *cl, *first = NULL;
struct timeval now;
RM_GETTIME(now);
if (op == CLASSQDQ_REMOVE && ifd->pollcache_) {
cl = ifd->pollcache_;
cpri = cl->pri_;
ifd->pollcache_ = NULL;
goto _prr_out;
} else {
ifd->pollcache_ = NULL;
ifd->borrowed_[ifd->qi_] = NULL;
}
#ifdef ADJUST_CUTOFF
_again:
#endif
for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) {
if (ifd->na_[cpri] == 0)
continue;
cl = ifd->active_[cpri];
VERIFY(cl != NULL);
do {
if (!qempty(&cl->q_)) {
if ((cl->undertime_.tv_sec == 0) ||
rmc_under_limit(cl, &now))
goto _prr_out;
if (first == NULL && cl->borrow_ != NULL)
first = cl;
}
cl = cl->peer_;
} while (cl != ifd->active_[cpri]);
}
#ifdef ADJUST_CUTOFF
if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) {
ifd->cutoff_++;
goto _again;
}
#endif
reset_cutoff(ifd);
if (!ifd->efficient_ || first == NULL)
return (NULL);
cl = first;
cpri = cl->pri_;
#if 0
if (cl->sleeping_)
CALLOUT_STOP(&cl->callout_);
cl->sleeping_ = 0;
cl->undertime_.tv_sec = 0;
#endif
ifd->borrowed_[ifd->qi_] = cl->borrow_;
ifd->cutoff_ = cl->borrow_->depth_;
_prr_out:
if (op == CLASSQDQ_REMOVE) {
m = _rmc_getq(cl);
if (m == NULL)
return (NULL);
if (qempty(&cl->q_))
ifd->na_[cpri]--;
ifd->active_[cpri] = cl->peer_;
ifd->class_[ifd->qi_] = cl;
ifd->curlen_[ifd->qi_] = m_pktlen(m);
ifd->now_[ifd->qi_] = now;
ifd->qi_ = (ifd->qi_ + 1) % ifd->maxqueued_;
ifd->queued_++;
} else {
m = _rmc_pollq(cl);
ifd->pollcache_ = cl;
}
return (m);
}
struct mbuf *
rmc_dequeue_next(struct rm_ifdat *ifd, cqdq_op_t mode)
{
if (ifd->queued_ >= ifd->maxqueued_)
return (NULL);
else if (ifd->wrr_)
return (_rmc_wrr_dequeue_next(ifd, mode));
else
return (_rmc_prr_dequeue_next(ifd, mode));
}
#define NSEC_TO_USEC(t) (((t) >> 10) + ((t) >> 16) + ((t) >> 17))
void
rmc_update_class_util(struct rm_ifdat *ifd)
{
int idle, avgidle, pktlen;
int pkt_time, tidle;
rm_class_t *cl, *borrowed;
rm_class_t *borrows;
struct timeval *nowp;
if ((cl = ifd->class_[ifd->qo_]) == NULL)
return;
pktlen = ifd->curlen_[ifd->qo_];
borrowed = ifd->borrowed_[ifd->qo_];
borrows = borrowed;
PKTCNTR_ADD(&cl->stats_.xmit_cnt, 1, pktlen);
nowp = &ifd->now_[ifd->qo_];
#if 1
pkt_time = ifd->curlen_[ifd->qo_] * ifd->ns_per_byte_;
pkt_time = NSEC_TO_USEC(pkt_time);
#else
pkt_time = ifd->curlen_[ifd->qo_] * ifd->ns_per_byte_ / 1000;
#endif
#if 1
if (TV_LT(nowp, &ifd->ifnow_)) {
int iftime;
TV_DELTA(&ifd->ifnow_, nowp, iftime);
if (iftime+pkt_time < ifd->maxiftime_) {
TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_);
} else {
TV_ADD_DELTA(nowp, ifd->maxiftime_, &ifd->ifnow_);
}
} else {
TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_);
}
#else
if (TV_LT(nowp, &ifd->ifnow_)) {
TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_);
} else {
TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_);
}
#endif
while (cl != NULL) {
TV_DELTA(&ifd->ifnow_, &cl->last_, idle);
if (idle >= 2000000)
cl->avgidle_ = cl->maxidle_;
#if 1
pkt_time = pktlen * cl->ns_per_byte_;
pkt_time = NSEC_TO_USEC(pkt_time);
#else
pkt_time = pktlen * cl->ns_per_byte_ / 1000;
#endif
idle -= pkt_time;
avgidle = cl->avgidle_;
avgidle += idle - (avgidle >> RM_FILTER_GAIN);
cl->avgidle_ = avgidle;
if (avgidle <= 0) {
CBQTRACE(rmc_update_class_util, 'milo',
cl->stats_.handle);
if (avgidle < cl->minidle_)
avgidle = cl->avgidle_ = cl->minidle_;
tidle = pkt_time +
(((1 - RM_POWER) * avgidle) >> RM_FILTER_GAIN);
TV_ADD_DELTA(nowp, tidle, &cl->undertime_);
++cl->stats_.over;
} else {
cl->avgidle_ =
(avgidle > cl->maxidle_) ? cl->maxidle_ : avgidle;
cl->undertime_.tv_sec = 0;
if (cl->sleeping_) {
CALLOUT_STOP(&cl->callout_);
cl->sleeping_ = 0;
}
}
if (borrows != NULL) {
if (borrows != cl)
++cl->stats_.borrows;
else
borrows = NULL;
}
cl->last_ = ifd->ifnow_;
cl->last_pkttime_ = pkt_time;
#if 1
if (cl->parent_ == NULL) {
PKTCNTR_ADD(&cl->stats_.xmit_cnt, 1, pktlen);
}
#endif
cl = cl->parent_;
}
cl = ifd->class_[ifd->qo_];
if (borrowed && (ifd->cutoff_ >= borrowed->depth_)) {
if ((qlen(&cl->q_) <= 0) ||
TV_LT(nowp, &borrowed->undertime_)) {
rmc_tl_satisfied(ifd, nowp);
CBQTRACE(rmc_update_class_util, 'broe', ifd->cutoff_);
} else {
ifd->cutoff_ = borrowed->depth_;
CBQTRACE(rmc_update_class_util, 'ffob',
borrowed->depth_);
}
}
ifd->borrowed_[ifd->qo_] = NULL;
ifd->class_[ifd->qo_] = NULL;
ifd->qo_ = (ifd->qo_ + 1) % ifd->maxqueued_;
ifd->queued_--;
}
static void
rmc_drop_action(struct rm_class *cl)
{
struct rm_ifdat *ifd = cl->ifdat_;
VERIFY(qlen(&cl->q_) > 0);
IFCQ_CONVERT_LOCK(ifd->ifq_);
_rmc_dropq(cl);
if (qempty(&cl->q_))
ifd->na_[cl->pri_]--;
}
void
rmc_drop(struct rm_class *cl, u_int32_t flow, u_int32_t *packets,
u_int32_t *bytes)
{
struct rm_ifdat *ifd = cl->ifdat_;
struct ifclassq *ifq = ifd->ifq_;
u_int32_t pkt = 0, len = 0, qlen;
if ((qlen = qlen(&cl->q_)) != 0) {
IFCQ_CONVERT_LOCK(ifq);
#if CLASSQ_RIO
if (q_is_rio(&cl->q_))
rio_purgeq(cl->rio_, &cl->q_, flow, &pkt, &len);
else
#endif
#if CLASSQ_RED
if (q_is_red(&cl->q_))
red_purgeq(cl->red_, &cl->q_, flow, &pkt, &len);
else
#endif
#if CLASSQ_BLUE
if (q_is_blue(&cl->q_))
blue_purgeq(cl->blue_, &cl->q_, flow, &pkt, &len);
else
#endif
if (q_is_sfb(&cl->q_) && cl->sfb_ != NULL)
sfb_purgeq(cl->sfb_, &cl->q_, flow, &pkt, &len);
else
_flushq_flow(&cl->q_, flow, &pkt, &len);
if (pkt > 0) {
VERIFY(qlen(&cl->q_) == (qlen - pkt));
PKTCNTR_ADD(&cl->stats_.drop_cnt, pkt, len);
IFCQ_DROP_ADD(ifq, pkt, len);
VERIFY(((signed)IFCQ_LEN(ifq) - pkt) >= 0);
IFCQ_LEN(ifq) -= pkt;
if (qempty(&cl->q_))
ifd->na_[cl->pri_]--;
}
}
if (packets != NULL)
*packets = pkt;
if (bytes != NULL)
*bytes = len;
}
void
rmc_dropall(struct rm_class *cl)
{
rmc_drop(cl, 0, NULL, NULL);
}
void
rmc_delay_action(struct rm_class *cl, struct rm_class *borrow)
{
int ndelay, t, extradelay;
cl->stats_.overactions++;
TV_DELTA(&cl->undertime_, &cl->overtime_, ndelay);
#ifndef BORROW_OFFTIME
ndelay += cl->offtime_;
#endif
if (!cl->sleeping_) {
CBQTRACE(rmc_delay_action, 'yled', cl->stats_.handle);
#ifdef BORROW_OFFTIME
if (borrow != NULL)
extradelay = borrow->offtime_;
else
#endif
extradelay = cl->offtime_;
extradelay -= cl->last_pkttime_;
if (extradelay > 0) {
TV_ADD_DELTA(&cl->undertime_, extradelay,
&cl->undertime_);
ndelay += extradelay;
}
cl->sleeping_ = 1;
cl->stats_.delays++;
if (ndelay > tick * 2) {
t = hzto(&cl->undertime_) + 1;
} else {
t = 2;
}
CALLOUT_RESET(&cl->callout_, t,
(timeout_t *)rmc_restart, (caddr_t)cl);
}
}
static void
rmc_restart(struct rm_class *cl)
{
struct rm_ifdat *ifd = cl->ifdat_;
if (cl->sleeping_) {
cl->sleeping_ = 0;
cl->undertime_.tv_sec = 0;
if (ifd->queued_ < ifd->maxqueued_ && ifd->restart != NULL) {
CBQTRACE(rmc_restart, 'trts', cl->stats_.handle);
(ifd->restart)(ifd->ifq_);
}
}
}
static void
rmc_root_overlimit(struct rm_class *cl,
struct rm_class *borrow)
{
#pragma unused(cl, borrow)
panic("rmc_root_overlimit");
}
static int
_rmc_addq(rm_class_t *cl, struct mbuf *m, struct pf_mtag *t)
{
#if CLASSQ_RIO
if (q_is_rio(&cl->q_))
return (rio_addq(cl->rio_, &cl->q_, m, t));
else
#endif
#if CLASSQ_RED
if (q_is_red(&cl->q_))
return (red_addq(cl->red_, &cl->q_, m, t));
else
#endif
#if CLASSQ_BLUE
if (q_is_blue(&cl->q_))
return (blue_addq(cl->blue_, &cl->q_, m, t));
else
#endif
if (q_is_sfb(&cl->q_)) {
if (cl->sfb_ == NULL) {
struct ifclassq *ifq = cl->ifdat_->ifq_;
struct ifnet *ifp = ifq->ifcq_ifp;
VERIFY(cl->flags_ & RMCF_LAZY);
IFCQ_CONVERT_LOCK(ifq);
cl->sfb_ = sfb_alloc(ifp, cl->stats_.handle,
qlimit(&cl->q_), cl->qflags_);
if (cl->sfb_ == NULL) {
qtype(&cl->q_) = Q_DROPTAIL;
cl->flags_ &= ~RMCF_SFB;
cl->qflags_ &= ~(SFBF_ECN | SFBF_FLOWCTL);
log(LOG_ERR, "%s: CBQ SFB lazy allocation "
"failed for qid=%d pri=%d, falling back "
"to DROPTAIL\n", if_name(ifp),
cl->stats_.handle, cl->pri_);
}
}
if (cl->sfb_ != NULL)
return (sfb_addq(cl->sfb_, &cl->q_, m, t));
}
#if PF_ECN
else if (cl->flags_ & RMCF_CLEARDSCP)
write_dsfield(m, t, 0);
#endif
_addq(&cl->q_, m);
return (0);
}
static void
_rmc_dropq(rm_class_t *cl)
{
struct mbuf *m;
if ((m = _rmc_getq(cl)) != NULL)
m_freem(m);
}
static struct mbuf *
_rmc_getq(rm_class_t *cl)
{
#if CLASSQ_RIO
if (q_is_rio(&cl->q_))
return (rio_getq(cl->rio_, &cl->q_));
else
#endif
#if CLASSQ_RED
if (q_is_red(&cl->q_))
return (red_getq(cl->red_, &cl->q_));
else
#endif
#if CLASSQ_BLUE
if (q_is_blue(&cl->q_))
return (blue_getq(cl->blue_, &cl->q_));
else
#endif
if (q_is_sfb(&cl->q_) && cl->sfb_ != NULL)
return (sfb_getq(cl->sfb_, &cl->q_));
return (_getq(&cl->q_));
}
static struct mbuf *
_rmc_pollq(rm_class_t *cl)
{
return (qhead(&cl->q_));
}
void
rmc_updateq(rm_class_t *cl, cqev_t ev)
{
#if CLASSQ_RIO
if (q_is_rio(&cl->q_))
return (rio_updateq(cl->rio_, ev));
#endif
#if CLASSQ_RED
if (q_is_red(&cl->q_))
return (red_updateq(cl->red_, ev));
#endif
#if CLASSQ_BLUE
if (q_is_blue(&cl->q_))
return (blue_updateq(cl->blue_, ev));
#endif
if (q_is_sfb(&cl->q_) && cl->sfb_ != NULL)
return (sfb_updateq(cl->sfb_, ev));
}
#ifdef CBQ_TRACE
struct cbqtrace cbqtrace_buffer[NCBQTRACE+1];
struct cbqtrace *cbqtrace_ptr = NULL;
int cbqtrace_count;
void cbqtrace_dump(int);
static char *rmc_funcname(void *);
static struct rmc_funcs {
void *func;
char *name;
} rmc_funcs[] =
{
rmc_init, "rmc_init",
rmc_queue_packet, "rmc_queue_packet",
rmc_under_limit, "rmc_under_limit",
rmc_update_class_util, "rmc_update_class_util",
rmc_delay_action, "rmc_delay_action",
rmc_restart, "rmc_restart",
_rmc_wrr_dequeue_next, "_rmc_wrr_dequeue_next",
NULL, NULL
};
static char *
rmc_funcname(void *func)
{
struct rmc_funcs *fp;
for (fp = rmc_funcs; fp->func != NULL; fp++)
if (fp->func == func)
return (fp->name);
return ("unknown");
}
void
cbqtrace_dump(int counter)
{
int i, *p;
char *cp;
counter = counter % NCBQTRACE;
p = (int *)&cbqtrace_buffer[counter];
for (i = 0; i < 20; i++) {
log(LOG_DEBUG, "[0x%x] ", *p++);
log(LOG_DEBUG, "%s: ", rmc_funcname((void *)*p++));
cp = (char *)p++;
log(LOG_DEBUG, "%c%c%c%c: ", cp[0], cp[1], cp[2], cp[3]);
log(LOG_DEBUG, "%d\n", *p++);
if (p >= (int *)&cbqtrace_buffer[NCBQTRACE])
p = (int *)cbqtrace_buffer;
}
}
#endif
#endif