Index: stable/11/sys/netpfil/ipfw/dn_sched_fifo.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_fifo.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_fifo.c (revision 325730) @@ -1,127 +1,130 @@ /* * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * $FreeBSD$ */ #ifdef _KERNEL #include #include #include #include +#include #include #include +#include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include +#include #include #include #ifdef NEW_AQM #include #endif #include #else #include #endif /* * This file implements a FIFO scheduler for a single queue. * The queue is allocated as part of the scheduler instance, * and there is a single flowset is in the template which stores * queue size and policy. * Enqueue and dequeue use the default library functions. */ static int fifo_enqueue(struct dn_sch_inst *si, struct dn_queue *q, struct mbuf *m) { /* XXX if called with q != NULL and m=NULL, this is a * re-enqueue from an existing scheduler, which we should * handle. */ (void)q; return dn_enqueue((struct dn_queue *)(si+1), m, 0); } static struct mbuf * fifo_dequeue(struct dn_sch_inst *si) { return dn_dequeue((struct dn_queue *)(si + 1)); } static int fifo_new_sched(struct dn_sch_inst *si) { /* This scheduler instance contains the queue */ struct dn_queue *q = (struct dn_queue *)(si + 1); set_oid(&q->ni.oid, DN_QUEUE, sizeof(*q)); q->_si = si; q->fs = si->sched->fs; return 0; } static int fifo_free_sched(struct dn_sch_inst *si) { struct dn_queue *q = (struct dn_queue *)(si + 1); dn_free_pkts(q->mq.head); bzero(q, sizeof(*q)); return 0; } /* * FIFO scheduler descriptor * contains the type of the scheduler, the name, the size of extra * data structures, and function pointers. */ static struct dn_alg fifo_desc = { _SI( .type = ) DN_SCHED_FIFO, _SI( .name = ) "FIFO", _SI( .flags = ) 0, _SI( .schk_datalen = ) 0, _SI( .si_datalen = ) sizeof(struct dn_queue), _SI( .q_datalen = ) 0, _SI( .enqueue = ) fifo_enqueue, _SI( .dequeue = ) fifo_dequeue, _SI( .config = ) NULL, _SI( .destroy = ) NULL, _SI( .new_sched = ) fifo_new_sched, _SI( .free_sched = ) fifo_free_sched, _SI( .new_fsk = ) NULL, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) NULL, _SI( .free_queue = ) NULL, #ifdef NEW_AQM _SI( .getconfig = ) NULL, #endif }; DECLARE_DNSCHED_MODULE(dn_fifo, &fifo_desc); Index: stable/11/sys/netpfil/ipfw/dn_sched_fq_codel.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_fq_codel.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_fq_codel.c (revision 325730) @@ -1,617 +1,617 @@ /* * FQ_Codel - The FlowQueue-Codel scheduler/AQM * * $FreeBSD$ * * Copyright (C) 2016 Centre for Advanced Internet Architectures, * Swinburne University of Technology, Melbourne, Australia. * Portions of this code were made possible in part by a gift from * The Comcast Innovation Fund. * Implemented by Rasool Al-Saadi * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ #ifdef _KERNEL #include #include //#include #include #include #include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #else #include #endif /* NOTE: In fq_codel module, we reimplements CoDel AQM functions * because fq_codel use different flows (sub-queues) structure and * dn_queue includes many variables not needed by a flow (sub-queue * )i.e. avoid extra overhead (88 bytes vs 208 bytes). * Also, CoDel functions manages stats of sub-queues as well as the main queue. */ #define DN_SCHED_FQ_CODEL 6 static struct dn_alg fq_codel_desc; /* fq_codel default parameters including codel */ struct dn_sch_fq_codel_parms fq_codel_sysctl = {{5000 * AQM_TIME_1US, 100000 * AQM_TIME_1US, CODEL_ECN_ENABLED}, 1024, 10240, 1514}; static int fqcodel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS) { int error; long value; value = fq_codel_sysctl.ccfg.interval; value /= AQM_TIME_1US; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 1 || value > 100 * AQM_TIME_1S) return (EINVAL); fq_codel_sysctl.ccfg.interval = value * AQM_TIME_1US ; return (0); } static int fqcodel_sysctl_target_handler(SYSCTL_HANDLER_ARGS) { int error; long value; value = fq_codel_sysctl.ccfg.target; value /= AQM_TIME_1US; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 1 || value > 5 * AQM_TIME_1S) return (EINVAL); fq_codel_sysctl.ccfg.target = value * AQM_TIME_1US ; return (0); } SYSBEGIN(f4) SYSCTL_DECL(_net_inet); SYSCTL_DECL(_net_inet_ip); SYSCTL_DECL(_net_inet_ip_dummynet); static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, fqcodel, CTLFLAG_RW, 0, "FQ_CODEL"); #ifdef SYSCTL_NODE SYSCTL_PROC(_net_inet_ip_dummynet_fqcodel, OID_AUTO, target, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqcodel_sysctl_target_handler, "L", "FQ_CoDel target in microsecond"); SYSCTL_PROC(_net_inet_ip_dummynet_fqcodel, OID_AUTO, interval, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqcodel_sysctl_interval_handler, "L", "FQ_CoDel interval in microsecond"); SYSCTL_UINT(_net_inet_ip_dummynet_fqcodel, OID_AUTO, quantum, CTLFLAG_RW, &fq_codel_sysctl.quantum, 1514, "FQ_CoDel quantum"); SYSCTL_UINT(_net_inet_ip_dummynet_fqcodel, OID_AUTO, flows, CTLFLAG_RW, &fq_codel_sysctl.flows_cnt, 1024, "Number of queues for FQ_CoDel"); SYSCTL_UINT(_net_inet_ip_dummynet_fqcodel, OID_AUTO, limit, CTLFLAG_RW, &fq_codel_sysctl.limit, 10240, "FQ_CoDel queues size limit"); #endif /* Drop a packet form the head of codel queue */ static void codel_drop_head(struct fq_codel_flow *q, struct fq_codel_si *si) { struct mbuf *m = q->mq.head; if (m == NULL) return; q->mq.head = m->m_nextpkt; fq_update_stats(q, si, -m->m_pkthdr.len, 1); if (si->main_q.ni.length == 0) /* queue is now idle */ si->main_q.q_time = dn_cfg.curr_time; FREE_PKT(m); } /* Enqueue a packet 'm' to a queue 'q' and add timestamp to that packet. * Return 1 when unable to add timestamp, otherwise return 0 */ static int codel_enqueue(struct fq_codel_flow *q, struct mbuf *m, struct fq_codel_si *si) { uint64_t len; len = m->m_pkthdr.len; /* finding maximum packet size */ if (len > q->cst.maxpkt_size) q->cst.maxpkt_size = len; /* Add timestamp to mbuf as MTAG */ struct m_tag *mtag; mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); if (mtag == NULL) mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, sizeof(aqm_time_t), M_NOWAIT); if (mtag == NULL) { m_freem(m); goto drop; } *(aqm_time_t *)(mtag + 1) = AQM_UNOW; m_tag_prepend(m, mtag); mq_append(&q->mq, m); fq_update_stats(q, si, len, 0); return 0; drop: fq_update_stats(q, si, len, 1); m_freem(m); return 1; } /* * Classify a packet to queue number using Jenkins hash function. * Return: queue number * the input of the hash are protocol no, perturbation, src IP, dst IP, * src port, dst port, */ static inline int fq_codel_classify_flow(struct mbuf *m, uint16_t fcount, struct fq_codel_si *si) { struct ip *ip; struct tcphdr *th; struct udphdr *uh; uint8_t tuple[41]; uint16_t hash=0; + ip = (struct ip *)mtodo(m, dn_tag_get(m)->iphdr_off); //#ifdef INET6 struct ip6_hdr *ip6; int isip6; - isip6 = (mtod(m, struct ip *)->ip_v == 6) ? 1 : 0; + isip6 = (ip->ip_v == 6); if(isip6) { - ip6 = mtod(m, struct ip6_hdr *); + ip6 = (struct ip6_hdr *)ip; *((uint8_t *) &tuple[0]) = ip6->ip6_nxt; *((uint32_t *) &tuple[1]) = si->perturbation; memcpy(&tuple[5], ip6->ip6_src.s6_addr, 16); memcpy(&tuple[21], ip6->ip6_dst.s6_addr, 16); switch (ip6->ip6_nxt) { case IPPROTO_TCP: th = (struct tcphdr *)(ip6 + 1); *((uint16_t *) &tuple[37]) = th->th_dport; *((uint16_t *) &tuple[39]) = th->th_sport; break; case IPPROTO_UDP: uh = (struct udphdr *)(ip6 + 1); *((uint16_t *) &tuple[37]) = uh->uh_dport; *((uint16_t *) &tuple[39]) = uh->uh_sport; break; default: memset(&tuple[37], 0, 4); } hash = jenkins_hash(tuple, 41, HASHINIT) % fcount; return hash; } //#endif /* IPv4 */ - ip = mtod(m, struct ip *); *((uint8_t *) &tuple[0]) = ip->ip_p; *((uint32_t *) &tuple[1]) = si->perturbation; *((uint32_t *) &tuple[5]) = ip->ip_src.s_addr; *((uint32_t *) &tuple[9]) = ip->ip_dst.s_addr; switch (ip->ip_p) { case IPPROTO_TCP: th = (struct tcphdr *)(ip + 1); *((uint16_t *) &tuple[13]) = th->th_dport; *((uint16_t *) &tuple[15]) = th->th_sport; break; case IPPROTO_UDP: uh = (struct udphdr *)(ip + 1); *((uint16_t *) &tuple[13]) = uh->uh_dport; *((uint16_t *) &tuple[15]) = uh->uh_sport; break; default: memset(&tuple[13], 0, 4); } hash = jenkins_hash(tuple, 17, HASHINIT) % fcount; return hash; } /* * Enqueue a packet into an appropriate queue according to * FQ_CODEL algorithm. */ static int fq_codel_enqueue(struct dn_sch_inst *_si, struct dn_queue *_q, struct mbuf *m) { struct fq_codel_si *si; struct fq_codel_schk *schk; struct dn_sch_fq_codel_parms *param; struct dn_queue *mainq; int idx, drop, i, maxidx; mainq = (struct dn_queue *)(_si + 1); si = (struct fq_codel_si *)_si; schk = (struct fq_codel_schk *)(si->_si.sched+1); param = &schk->cfg; /* classify a packet to queue number*/ idx = fq_codel_classify_flow(m, param->flows_cnt, si); /* enqueue packet into appropriate queue using CoDel AQM. * Note: 'codel_enqueue' function returns 1 only when it unable to * add timestamp to packet (no limit check)*/ drop = codel_enqueue(&si->flows[idx], m, si); /* codel unable to timestamp a packet */ if (drop) return 1; /* If the flow (sub-queue) is not active ,then add it to the tail of * new flows list, initialize and activate it. */ if (!si->flows[idx].active ) { STAILQ_INSERT_TAIL(&si->newflows, &si->flows[idx], flowchain); si->flows[idx].deficit = param->quantum; si->flows[idx].cst.dropping = false; si->flows[idx].cst.first_above_time = 0; si->flows[idx].active = 1; //D("activate %d",idx); } /* check the limit for all queues and remove a packet from the * largest one */ if (mainq->ni.length > schk->cfg.limit) { D("over limit"); /* find first active flow */ for (maxidx = 0; maxidx < schk->cfg.flows_cnt; maxidx++) if (si->flows[maxidx].active) break; if (maxidx < schk->cfg.flows_cnt) { /* find the largest sub- queue */ for (i = maxidx + 1; i < schk->cfg.flows_cnt; i++) if (si->flows[i].active && si->flows[i].stats.length > si->flows[maxidx].stats.length) maxidx = i; codel_drop_head(&si->flows[maxidx], si); D("maxidx = %d",maxidx); drop = 1; } } return drop; } /* * Dequeue a packet from an appropriate queue according to * FQ_CODEL algorithm. */ static struct mbuf * fq_codel_dequeue(struct dn_sch_inst *_si) { struct fq_codel_si *si; struct fq_codel_schk *schk; struct dn_sch_fq_codel_parms *param; struct fq_codel_flow *f; struct mbuf *mbuf; struct fq_codel_list *fq_codel_flowlist; si = (struct fq_codel_si *)_si; schk = (struct fq_codel_schk *)(si->_si.sched+1); param = &schk->cfg; do { /* select a list to start with */ if (STAILQ_EMPTY(&si->newflows)) fq_codel_flowlist = &si->oldflows; else fq_codel_flowlist = &si->newflows; /* Both new and old queue lists are empty, return NULL */ if (STAILQ_EMPTY(fq_codel_flowlist)) return NULL; f = STAILQ_FIRST(fq_codel_flowlist); while (f != NULL) { /* if there is no flow(sub-queue) deficit, increase deficit * by quantum, move the flow to the tail of old flows list * and try another flow. * Otherwise, the flow will be used for dequeue. */ if (f->deficit < 0) { f->deficit += param->quantum; STAILQ_REMOVE_HEAD(fq_codel_flowlist, flowchain); STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain); } else break; f = STAILQ_FIRST(fq_codel_flowlist); } /* the new flows list is empty, try old flows list */ if (STAILQ_EMPTY(fq_codel_flowlist)) continue; /* Dequeue a packet from the selected flow */ mbuf = fqc_codel_dequeue(f, si); /* Codel did not return a packet */ if (!mbuf) { /* If the selected flow belongs to new flows list, then move * it to the tail of old flows list. Otherwise, deactivate it and * remove it from the old list and */ if (fq_codel_flowlist == &si->newflows) { STAILQ_REMOVE_HEAD(fq_codel_flowlist, flowchain); STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain); } else { f->active = 0; STAILQ_REMOVE_HEAD(fq_codel_flowlist, flowchain); } /* start again */ continue; } /* we have a packet to return, * update flow deficit and return the packet*/ f->deficit -= mbuf->m_pkthdr.len; return mbuf; } while (1); /* unreachable point */ return NULL; } /* * Initialize fq_codel scheduler instance. * also, allocate memory for flows array. */ static int fq_codel_new_sched(struct dn_sch_inst *_si) { struct fq_codel_si *si; struct dn_queue *q; struct fq_codel_schk *schk; int i; si = (struct fq_codel_si *)_si; schk = (struct fq_codel_schk *)(_si->sched+1); if(si->flows) { D("si already configured!"); return 0; } /* init the main queue */ q = &si->main_q; set_oid(&q->ni.oid, DN_QUEUE, sizeof(*q)); q->_si = _si; q->fs = _si->sched->fs; /* allocate memory for flows array */ si->flows = malloc(schk->cfg.flows_cnt * sizeof(struct fq_codel_flow), M_DUMMYNET, M_NOWAIT | M_ZERO); if (si->flows == NULL) { D("cannot allocate memory for fq_codel configuration parameters"); return ENOMEM ; } /* init perturbation for this si */ si->perturbation = random(); /* init the old and new flows lists */ STAILQ_INIT(&si->newflows); STAILQ_INIT(&si->oldflows); /* init the flows (sub-queues) */ for (i = 0; i < schk->cfg.flows_cnt; i++) { /* init codel */ si->flows[i].cst.maxpkt_size = 500; } fq_codel_desc.ref_count++; return 0; } /* * Free fq_codel scheduler instance. */ static int fq_codel_free_sched(struct dn_sch_inst *_si) { struct fq_codel_si *si = (struct fq_codel_si *)_si ; /* free the flows array */ free(si->flows , M_DUMMYNET); si->flows = NULL; fq_codel_desc.ref_count--; return 0; } /* * Configure fq_codel scheduler. * the configurations for the scheduler is passed from userland. */ static int fq_codel_config(struct dn_schk *_schk) { struct fq_codel_schk *schk; struct dn_extra_parms *ep; struct dn_sch_fq_codel_parms *fqc_cfg; schk = (struct fq_codel_schk *)(_schk+1); ep = (struct dn_extra_parms *) _schk->cfg; /* par array contains fq_codel configuration as follow * Codel: 0- target,1- interval, 2- flags * FQ_CODEL: 3- quantum, 4- limit, 5- flows */ if (ep && ep->oid.len ==sizeof(*ep) && ep->oid.subtype == DN_SCH_PARAMS) { fqc_cfg = &schk->cfg; if (ep->par[0] < 0) fqc_cfg->ccfg.target = fq_codel_sysctl.ccfg.target; else fqc_cfg->ccfg.target = ep->par[0] * AQM_TIME_1US; if (ep->par[1] < 0) fqc_cfg->ccfg.interval = fq_codel_sysctl.ccfg.interval; else fqc_cfg->ccfg.interval = ep->par[1] * AQM_TIME_1US; if (ep->par[2] < 0) fqc_cfg->ccfg.flags = 0; else fqc_cfg->ccfg.flags = ep->par[2]; /* FQ configurations */ if (ep->par[3] < 0) fqc_cfg->quantum = fq_codel_sysctl.quantum; else fqc_cfg->quantum = ep->par[3]; if (ep->par[4] < 0) fqc_cfg->limit = fq_codel_sysctl.limit; else fqc_cfg->limit = ep->par[4]; if (ep->par[5] < 0) fqc_cfg->flows_cnt = fq_codel_sysctl.flows_cnt; else fqc_cfg->flows_cnt = ep->par[5]; /* Bound the configurations */ fqc_cfg->ccfg.target = BOUND_VAR(fqc_cfg->ccfg.target, 1 , 5 * AQM_TIME_1S); ; fqc_cfg->ccfg.interval = BOUND_VAR(fqc_cfg->ccfg.interval, 1, 100 * AQM_TIME_1S); fqc_cfg->quantum = BOUND_VAR(fqc_cfg->quantum,1, 9000); fqc_cfg->limit= BOUND_VAR(fqc_cfg->limit,1,20480); fqc_cfg->flows_cnt= BOUND_VAR(fqc_cfg->flows_cnt,1,65536); } else return 1; return 0; } /* * Return fq_codel scheduler configurations * the configurations for the scheduler is passed to userland. */ static int fq_codel_getconfig (struct dn_schk *_schk, struct dn_extra_parms *ep) { struct fq_codel_schk *schk = (struct fq_codel_schk *)(_schk+1); struct dn_sch_fq_codel_parms *fqc_cfg; fqc_cfg = &schk->cfg; strcpy(ep->name, fq_codel_desc.name); ep->par[0] = fqc_cfg->ccfg.target / AQM_TIME_1US; ep->par[1] = fqc_cfg->ccfg.interval / AQM_TIME_1US; ep->par[2] = fqc_cfg->ccfg.flags; ep->par[3] = fqc_cfg->quantum; ep->par[4] = fqc_cfg->limit; ep->par[5] = fqc_cfg->flows_cnt; return 0; } /* * fq_codel scheduler descriptor * contains the type of the scheduler, the name, the size of extra * data structures, and function pointers. */ static struct dn_alg fq_codel_desc = { _SI( .type = ) DN_SCHED_FQ_CODEL, _SI( .name = ) "FQ_CODEL", _SI( .flags = ) 0, _SI( .schk_datalen = ) sizeof(struct fq_codel_schk), _SI( .si_datalen = ) sizeof(struct fq_codel_si) - sizeof(struct dn_sch_inst), _SI( .q_datalen = ) 0, _SI( .enqueue = ) fq_codel_enqueue, _SI( .dequeue = ) fq_codel_dequeue, _SI( .config = ) fq_codel_config, /* new sched i.e. sched X config ...*/ _SI( .destroy = ) NULL, /*sched x delete */ _SI( .new_sched = ) fq_codel_new_sched, /* new schd instance */ _SI( .free_sched = ) fq_codel_free_sched, /* delete schd instance */ _SI( .new_fsk = ) NULL, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) NULL, _SI( .free_queue = ) NULL, _SI( .getconfig = ) fq_codel_getconfig, _SI( .ref_count = ) 0 }; DECLARE_DNSCHED_MODULE(dn_fq_codel, &fq_codel_desc); Index: stable/11/sys/netpfil/ipfw/dn_sched_fq_pie.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_fq_pie.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_fq_pie.c (revision 325730) @@ -1,1235 +1,1235 @@ /* * FQ_PIE - The FlowQueue-PIE scheduler/AQM * * $FreeBSD$ * * Copyright (C) 2016 Centre for Advanced Internet Architectures, * Swinburne University of Technology, Melbourne, Australia. * Portions of this code were made possible in part by a gift from * The Comcast Innovation Fund. * Implemented by Rasool Al-Saadi * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* Important note: * As there is no an office document for FQ-PIE specification, we used * FQ-CoDel algorithm with some modifications to implement FQ-PIE. * This FQ-PIE implementation is a beta version and have not been tested * extensively. Our FQ-PIE uses stand-alone PIE AQM per sub-queue. By * default, timestamp is used to calculate queue delay instead of departure * rate estimation method. Although departure rate estimation is available * as testing option, the results could be incorrect. Moreover, turning PIE on * and off option is available but it does not work properly in this version. */ #ifdef _KERNEL #include #include #include #include #include #include #include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #else #include #endif #define DN_SCHED_FQ_PIE 7 /* list of queues */ STAILQ_HEAD(fq_pie_list, fq_pie_flow) ; /* FQ_PIE parameters including PIE */ struct dn_sch_fq_pie_parms { struct dn_aqm_pie_parms pcfg; /* PIE configuration Parameters */ /* FQ_PIE Parameters */ uint32_t flows_cnt; /* number of flows */ uint32_t limit; /* hard limit of FQ_PIE queue size*/ uint32_t quantum; }; /* flow (sub-queue) stats */ struct flow_stats { uint64_t tot_pkts; /* statistics counters */ uint64_t tot_bytes; uint32_t length; /* Queue length, in packets */ uint32_t len_bytes; /* Queue length, in bytes */ uint32_t drops; }; /* A flow of packets (sub-queue)*/ struct fq_pie_flow { struct mq mq; /* list of packets */ struct flow_stats stats; /* statistics */ int deficit; int active; /* 1: flow is active (in a list) */ struct pie_status pst; /* pie status variables */ struct fq_pie_si_extra *psi_extra; STAILQ_ENTRY(fq_pie_flow) flowchain; }; /* extra fq_pie scheduler configurations */ struct fq_pie_schk { struct dn_sch_fq_pie_parms cfg; }; /* fq_pie scheduler instance extra state vars. * The purpose of separation this structure is to preserve number of active * sub-queues and the flows array pointer even after the scheduler instance * is destroyed. * Preserving these varaiables allows freeing the allocated memory by * fqpie_callout_cleanup() independently from fq_pie_free_sched(). */ struct fq_pie_si_extra { uint32_t nr_active_q; /* number of active queues */ struct fq_pie_flow *flows; /* array of flows (queues) */ }; /* fq_pie scheduler instance */ struct fq_pie_si { struct dn_sch_inst _si; /* standard scheduler instance. SHOULD BE FIRST */ struct dn_queue main_q; /* main queue is after si directly */ uint32_t perturbation; /* random value */ struct fq_pie_list newflows; /* list of new queues */ struct fq_pie_list oldflows; /* list of old queues */ struct fq_pie_si_extra *si_extra; /* extra state vars*/ }; static struct dn_alg fq_pie_desc; /* Default FQ-PIE parameters including PIE */ /* PIE defaults * target=15ms, max_burst=150ms, max_ecnth=0.1, * alpha=0.125, beta=1.25, tupdate=15ms * FQ- * flows=1024, limit=10240, quantum =1514 */ struct dn_sch_fq_pie_parms fq_pie_sysctl = {{15000 * AQM_TIME_1US, 15000 * AQM_TIME_1US, 150000 * AQM_TIME_1US, PIE_SCALE * 0.1, PIE_SCALE * 0.125, PIE_SCALE * 1.25, PIE_CAPDROP_ENABLED | PIE_DERAND_ENABLED}, 1024, 10240, 1514}; static int fqpie_sysctl_alpha_beta_handler(SYSCTL_HANDLER_ARGS) { int error; long value; if (!strcmp(oidp->oid_name,"alpha")) value = fq_pie_sysctl.pcfg.alpha; else value = fq_pie_sysctl.pcfg.beta; value = value * 1000 / PIE_SCALE; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 1 || value > 7 * PIE_SCALE) return (EINVAL); value = (value * PIE_SCALE) / 1000; if (!strcmp(oidp->oid_name,"alpha")) fq_pie_sysctl.pcfg.alpha = value; else fq_pie_sysctl.pcfg.beta = value; return (0); } static int fqpie_sysctl_target_tupdate_maxb_handler(SYSCTL_HANDLER_ARGS) { int error; long value; if (!strcmp(oidp->oid_name,"target")) value = fq_pie_sysctl.pcfg.qdelay_ref; else if (!strcmp(oidp->oid_name,"tupdate")) value = fq_pie_sysctl.pcfg.tupdate; else value = fq_pie_sysctl.pcfg.max_burst; value = value / AQM_TIME_1US; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 1 || value > 10 * AQM_TIME_1S) return (EINVAL); value = value * AQM_TIME_1US; if (!strcmp(oidp->oid_name,"target")) fq_pie_sysctl.pcfg.qdelay_ref = value; else if (!strcmp(oidp->oid_name,"tupdate")) fq_pie_sysctl.pcfg.tupdate = value; else fq_pie_sysctl.pcfg.max_burst = value; return (0); } static int fqpie_sysctl_max_ecnth_handler(SYSCTL_HANDLER_ARGS) { int error; long value; value = fq_pie_sysctl.pcfg.max_ecnth; value = value * 1000 / PIE_SCALE; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 1 || value > PIE_SCALE) return (EINVAL); value = (value * PIE_SCALE) / 1000; fq_pie_sysctl.pcfg.max_ecnth = value; return (0); } /* define FQ- PIE sysctl variables */ SYSBEGIN(f4) SYSCTL_DECL(_net_inet); SYSCTL_DECL(_net_inet_ip); SYSCTL_DECL(_net_inet_ip_dummynet); static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, fqpie, CTLFLAG_RW, 0, "FQ_PIE"); #ifdef SYSCTL_NODE SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, target, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_target_tupdate_maxb_handler, "L", "queue target in microsecond"); SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, tupdate, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_target_tupdate_maxb_handler, "L", "the frequency of drop probability calculation in microsecond"); SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_burst, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_target_tupdate_maxb_handler, "L", "Burst allowance interval in microsecond"); SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, max_ecnth, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_max_ecnth_handler, "L", "ECN safeguard threshold scaled by 1000"); SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, alpha, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_alpha_beta_handler, "L", "PIE alpha scaled by 1000"); SYSCTL_PROC(_net_inet_ip_dummynet_fqpie, OID_AUTO, beta, CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, fqpie_sysctl_alpha_beta_handler, "L", "beta scaled by 1000"); SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, quantum, CTLFLAG_RW, &fq_pie_sysctl.quantum, 1514, "quantum for FQ_PIE"); SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, flows, CTLFLAG_RW, &fq_pie_sysctl.flows_cnt, 1024, "Number of queues for FQ_PIE"); SYSCTL_UINT(_net_inet_ip_dummynet_fqpie, OID_AUTO, limit, CTLFLAG_RW, &fq_pie_sysctl.limit, 10240, "limit for FQ_PIE"); #endif /* Helper function to update queue&main-queue and scheduler statistics. * negative len & drop -> drop * negative len -> dequeue * positive len -> enqueue * positive len + drop -> drop during enqueue */ __inline static void fq_update_stats(struct fq_pie_flow *q, struct fq_pie_si *si, int len, int drop) { int inc = 0; if (len < 0) inc = -1; else if (len > 0) inc = 1; if (drop) { si->main_q.ni.drops ++; q->stats.drops ++; si->_si.ni.drops ++; io_pkt_drop ++; } if (!drop || (drop && len < 0)) { /* Update stats for the main queue */ si->main_q.ni.length += inc; si->main_q.ni.len_bytes += len; /*update sub-queue stats */ q->stats.length += inc; q->stats.len_bytes += len; /*update scheduler instance stats */ si->_si.ni.length += inc; si->_si.ni.len_bytes += len; } if (inc > 0) { si->main_q.ni.tot_bytes += len; si->main_q.ni.tot_pkts ++; q->stats.tot_bytes +=len; q->stats.tot_pkts++; si->_si.ni.tot_bytes +=len; si->_si.ni.tot_pkts ++; } } /* * Extract a packet from the head of sub-queue 'q' * Return a packet or NULL if the queue is empty. * If getts is set, also extract packet's timestamp from mtag. */ __inline static struct mbuf * fq_pie_extract_head(struct fq_pie_flow *q, aqm_time_t *pkt_ts, struct fq_pie_si *si, int getts) { struct mbuf *m = q->mq.head; if (m == NULL) return m; q->mq.head = m->m_nextpkt; fq_update_stats(q, si, -m->m_pkthdr.len, 0); if (si->main_q.ni.length == 0) /* queue is now idle */ si->main_q.q_time = dn_cfg.curr_time; if (getts) { /* extract packet timestamp*/ struct m_tag *mtag; mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); if (mtag == NULL){ D("PIE timestamp mtag not found!"); *pkt_ts = 0; } else { *pkt_ts = *(aqm_time_t *)(mtag + 1); m_tag_delete(m,mtag); } } return m; } /* * Callout function for drop probability calculation * This function is called over tupdate ms and takes pointer of FQ-PIE * flow as an argument */ static void fq_calculate_drop_prob(void *x) { struct fq_pie_flow *q = (struct fq_pie_flow *) x; struct pie_status *pst = &q->pst; struct dn_aqm_pie_parms *pprms; int64_t p, prob, oldprob; aqm_time_t now; int p_isneg; now = AQM_UNOW; pprms = pst->parms; prob = pst->drop_prob; /* calculate current qdelay using DRE method. * If TS is used and no data in the queue, reset current_qdelay * as it stays at last value during dequeue process. */ if (pprms->flags & PIE_DEPRATEEST_ENABLED) pst->current_qdelay = ((uint64_t)q->stats.len_bytes * pst->avg_dq_time) >> PIE_DQ_THRESHOLD_BITS; else if (!q->stats.len_bytes) pst->current_qdelay = 0; /* calculate drop probability */ p = (int64_t)pprms->alpha * ((int64_t)pst->current_qdelay - (int64_t)pprms->qdelay_ref); p +=(int64_t) pprms->beta * ((int64_t)pst->current_qdelay - (int64_t)pst->qdelay_old); /* take absolute value so right shift result is well defined */ p_isneg = p < 0; if (p_isneg) { p = -p; } /* We PIE_MAX_PROB shift by 12-bits to increase the division precision */ p *= (PIE_MAX_PROB << 12) / AQM_TIME_1S; /* auto-tune drop probability */ if (prob < (PIE_MAX_PROB / 1000000)) /* 0.000001 */ p >>= 11 + PIE_FIX_POINT_BITS + 12; else if (prob < (PIE_MAX_PROB / 100000)) /* 0.00001 */ p >>= 9 + PIE_FIX_POINT_BITS + 12; else if (prob < (PIE_MAX_PROB / 10000)) /* 0.0001 */ p >>= 7 + PIE_FIX_POINT_BITS + 12; else if (prob < (PIE_MAX_PROB / 1000)) /* 0.001 */ p >>= 5 + PIE_FIX_POINT_BITS + 12; else if (prob < (PIE_MAX_PROB / 100)) /* 0.01 */ p >>= 3 + PIE_FIX_POINT_BITS + 12; else if (prob < (PIE_MAX_PROB / 10)) /* 0.1 */ p >>= 1 + PIE_FIX_POINT_BITS + 12; else p >>= PIE_FIX_POINT_BITS + 12; oldprob = prob; if (p_isneg) { prob = prob - p; /* check for multiplication underflow */ if (prob > oldprob) { prob= 0; D("underflow"); } } else { /* Cap Drop adjustment */ if ((pprms->flags & PIE_CAPDROP_ENABLED) && prob >= PIE_MAX_PROB / 10 && p > PIE_MAX_PROB / 50 ) { p = PIE_MAX_PROB / 50; } prob = prob + p; /* check for multiplication overflow */ if (probcurrent_qdelay == 0 && pst->qdelay_old == 0) { /* 0.98 ~= 1- 1/64 */ prob = prob - (prob >> 6); } if (prob > PIE_MAX_PROB) { prob = PIE_MAX_PROB; } } pst->drop_prob = prob; /* store current delay value */ pst->qdelay_old = pst->current_qdelay; /* update burst allowance */ if ((pst->sflags & PIE_ACTIVE) && pst->burst_allowance) { if (pst->burst_allowance > pprms->tupdate) pst->burst_allowance -= pprms->tupdate; else pst->burst_allowance = 0; } if (pst->sflags & PIE_ACTIVE) callout_reset_sbt(&pst->aqm_pie_callout, (uint64_t)pprms->tupdate * SBT_1US, 0, fq_calculate_drop_prob, q, 0); mtx_unlock(&pst->lock_mtx); } /* * Reset PIE variables & activate the queue */ __inline static void fq_activate_pie(struct fq_pie_flow *q) { struct pie_status *pst = &q->pst; struct dn_aqm_pie_parms *pprms; mtx_lock(&pst->lock_mtx); pprms = pst->parms; pprms = pst->parms; pst->drop_prob = 0; pst->qdelay_old = 0; pst->burst_allowance = pprms->max_burst; pst->accu_prob = 0; pst->dq_count = 0; pst->avg_dq_time = 0; pst->sflags = PIE_INMEASUREMENT | PIE_ACTIVE; pst->measurement_start = AQM_UNOW; callout_reset_sbt(&pst->aqm_pie_callout, (uint64_t)pprms->tupdate * SBT_1US, 0, fq_calculate_drop_prob, q, 0); mtx_unlock(&pst->lock_mtx); } /* * Deactivate PIE and stop probe update callout */ __inline static void fq_deactivate_pie(struct pie_status *pst) { mtx_lock(&pst->lock_mtx); pst->sflags &= ~(PIE_ACTIVE | PIE_INMEASUREMENT); callout_stop(&pst->aqm_pie_callout); //D("PIE Deactivated"); mtx_unlock(&pst->lock_mtx); } /* * Initialize PIE for sub-queue 'q' */ static int pie_init(struct fq_pie_flow *q, struct fq_pie_schk *fqpie_schk) { struct pie_status *pst=&q->pst; struct dn_aqm_pie_parms *pprms = pst->parms; int err = 0; if (!pprms){ D("AQM_PIE is not configured"); err = EINVAL; } else { q->psi_extra->nr_active_q++; /* For speed optimization, we caculate 1/3 queue size once here */ // XXX limit divided by number of queues divided by 3 ??? pst->one_third_q_size = (fqpie_schk->cfg.limit / fqpie_schk->cfg.flows_cnt) / 3; mtx_init(&pst->lock_mtx, "mtx_pie", NULL, MTX_DEF); callout_init_mtx(&pst->aqm_pie_callout, &pst->lock_mtx, CALLOUT_RETURNUNLOCKED); } return err; } /* * callout function to destroy PIE lock, and free fq_pie flows and fq_pie si * extra memory when number of active sub-queues reaches zero. * 'x' is a fq_pie_flow to be destroyed */ static void fqpie_callout_cleanup(void *x) { struct fq_pie_flow *q = x; struct pie_status *pst = &q->pst; struct fq_pie_si_extra *psi_extra; mtx_unlock(&pst->lock_mtx); mtx_destroy(&pst->lock_mtx); psi_extra = q->psi_extra; DN_BH_WLOCK(); psi_extra->nr_active_q--; /* when all sub-queues are destroyed, free flows fq_pie extra vars memory */ if (!psi_extra->nr_active_q) { free(psi_extra->flows, M_DUMMYNET); free(psi_extra, M_DUMMYNET); fq_pie_desc.ref_count--; } DN_BH_WUNLOCK(); } /* * Clean up PIE status for sub-queue 'q' * Stop callout timer and destroy mtx using fqpie_callout_cleanup() callout. */ static int pie_cleanup(struct fq_pie_flow *q) { struct pie_status *pst = &q->pst; mtx_lock(&pst->lock_mtx); callout_reset_sbt(&pst->aqm_pie_callout, SBT_1US, 0, fqpie_callout_cleanup, q, 0); mtx_unlock(&pst->lock_mtx); return 0; } /* * Dequeue and return a pcaket from sub-queue 'q' or NULL if 'q' is empty. * Also, caculate depature time or queue delay using timestamp */ static struct mbuf * pie_dequeue(struct fq_pie_flow *q, struct fq_pie_si *si) { struct mbuf *m; struct dn_aqm_pie_parms *pprms; struct pie_status *pst; aqm_time_t now; aqm_time_t pkt_ts, dq_time; int32_t w; pst = &q->pst; pprms = q->pst.parms; /*we extarct packet ts only when Departure Rate Estimation dis not used*/ m = fq_pie_extract_head(q, &pkt_ts, si, !(pprms->flags & PIE_DEPRATEEST_ENABLED)); if (!m || !(pst->sflags & PIE_ACTIVE)) return m; now = AQM_UNOW; if (pprms->flags & PIE_DEPRATEEST_ENABLED) { /* calculate average depature time */ if(pst->sflags & PIE_INMEASUREMENT) { pst->dq_count += m->m_pkthdr.len; if (pst->dq_count >= PIE_DQ_THRESHOLD) { dq_time = now - pst->measurement_start; /* * if we don't have old avg dq_time i.e PIE is (re)initialized, * don't use weight to calculate new avg_dq_time */ if(pst->avg_dq_time == 0) pst->avg_dq_time = dq_time; else { /* * weight = PIE_DQ_THRESHOLD/2^6, but we scaled * weight by 2^8. Thus, scaled * weight = PIE_DQ_THRESHOLD /2^8 * */ w = PIE_DQ_THRESHOLD >> 8; pst->avg_dq_time = (dq_time* w + (pst->avg_dq_time * ((1L << 8) - w))) >> 8; pst->sflags &= ~PIE_INMEASUREMENT; } } } /* * Start new measurment cycle when the queue has * PIE_DQ_THRESHOLD worth of bytes. */ if(!(pst->sflags & PIE_INMEASUREMENT) && q->stats.len_bytes >= PIE_DQ_THRESHOLD) { pst->sflags |= PIE_INMEASUREMENT; pst->measurement_start = now; pst->dq_count = 0; } } /* Optionally, use packet timestamp to estimate queue delay */ else pst->current_qdelay = now - pkt_ts; return m; } /* * Enqueue a packet in q, subject to space and FQ-PIE queue management policy * (whose parameters are in q->fs). * Update stats for the queue and the scheduler. * Return 0 on success, 1 on drop. The packet is consumed anyways. */ static int pie_enqueue(struct fq_pie_flow *q, struct mbuf* m, struct fq_pie_si *si) { uint64_t len; struct pie_status *pst; struct dn_aqm_pie_parms *pprms; int t; len = m->m_pkthdr.len; pst = &q->pst; pprms = pst->parms; t = ENQUE; /* drop/mark the packet when PIE is active and burst time elapsed */ if (pst->sflags & PIE_ACTIVE && pst->burst_allowance == 0 && drop_early(pst, q->stats.len_bytes) == DROP) { /* * if drop_prob over ECN threshold, drop the packet * otherwise mark and enqueue it. */ if (pprms->flags & PIE_ECN_ENABLED && pst->drop_prob < (pprms->max_ecnth << (PIE_PROB_BITS - PIE_FIX_POINT_BITS)) && ecn_mark(m)) t = ENQUE; else t = DROP; } /* Turn PIE on when 1/3 of the queue is full */ if (!(pst->sflags & PIE_ACTIVE) && q->stats.len_bytes >= pst->one_third_q_size) { fq_activate_pie(q); } /* reset burst tolerance and optinally turn PIE off*/ if (pst->drop_prob == 0 && pst->current_qdelay < (pprms->qdelay_ref >> 1) && pst->qdelay_old < (pprms->qdelay_ref >> 1)) { pst->burst_allowance = pprms->max_burst; if (pprms->flags & PIE_ON_OFF_MODE_ENABLED && q->stats.len_bytes<=0) fq_deactivate_pie(pst); } /* Use timestamp if Departure Rate Estimation mode is disabled */ if (t != DROP && !(pprms->flags & PIE_DEPRATEEST_ENABLED)) { /* Add TS to mbuf as a TAG */ struct m_tag *mtag; mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); if (mtag == NULL) mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, sizeof(aqm_time_t), M_NOWAIT); if (mtag == NULL) { m_freem(m); t = DROP; } *(aqm_time_t *)(mtag + 1) = AQM_UNOW; m_tag_prepend(m, mtag); } if (t != DROP) { mq_append(&q->mq, m); fq_update_stats(q, si, len, 0); return 0; } else { fq_update_stats(q, si, len, 1); pst->accu_prob = 0; FREE_PKT(m); return 1; } return 0; } /* Drop a packet form the head of FQ-PIE sub-queue */ static void pie_drop_head(struct fq_pie_flow *q, struct fq_pie_si *si) { struct mbuf *m = q->mq.head; if (m == NULL) return; q->mq.head = m->m_nextpkt; fq_update_stats(q, si, -m->m_pkthdr.len, 1); if (si->main_q.ni.length == 0) /* queue is now idle */ si->main_q.q_time = dn_cfg.curr_time; /* reset accu_prob after packet drop */ q->pst.accu_prob = 0; FREE_PKT(m); } /* * Classify a packet to queue number using Jenkins hash function. * Return: queue number * the input of the hash are protocol no, perturbation, src IP, dst IP, * src port, dst port, */ static inline int fq_pie_classify_flow(struct mbuf *m, uint16_t fcount, struct fq_pie_si *si) { struct ip *ip; struct tcphdr *th; struct udphdr *uh; uint8_t tuple[41]; uint16_t hash=0; + ip = (struct ip *)mtodo(m, dn_tag_get(m)->iphdr_off); //#ifdef INET6 struct ip6_hdr *ip6; int isip6; - isip6 = (mtod(m, struct ip *)->ip_v == 6) ? 1 : 0; + isip6 = (ip->ip_v == 6); if(isip6) { - ip6 = mtod(m, struct ip6_hdr *); + ip6 = (struct ip6_hdr *)ip; *((uint8_t *) &tuple[0]) = ip6->ip6_nxt; *((uint32_t *) &tuple[1]) = si->perturbation; memcpy(&tuple[5], ip6->ip6_src.s6_addr, 16); memcpy(&tuple[21], ip6->ip6_dst.s6_addr, 16); switch (ip6->ip6_nxt) { case IPPROTO_TCP: th = (struct tcphdr *)(ip6 + 1); *((uint16_t *) &tuple[37]) = th->th_dport; *((uint16_t *) &tuple[39]) = th->th_sport; break; case IPPROTO_UDP: uh = (struct udphdr *)(ip6 + 1); *((uint16_t *) &tuple[37]) = uh->uh_dport; *((uint16_t *) &tuple[39]) = uh->uh_sport; break; default: memset(&tuple[37], 0, 4); } hash = jenkins_hash(tuple, 41, HASHINIT) % fcount; return hash; } //#endif /* IPv4 */ - ip = mtod(m, struct ip *); *((uint8_t *) &tuple[0]) = ip->ip_p; *((uint32_t *) &tuple[1]) = si->perturbation; *((uint32_t *) &tuple[5]) = ip->ip_src.s_addr; *((uint32_t *) &tuple[9]) = ip->ip_dst.s_addr; switch (ip->ip_p) { case IPPROTO_TCP: th = (struct tcphdr *)(ip + 1); *((uint16_t *) &tuple[13]) = th->th_dport; *((uint16_t *) &tuple[15]) = th->th_sport; break; case IPPROTO_UDP: uh = (struct udphdr *)(ip + 1); *((uint16_t *) &tuple[13]) = uh->uh_dport; *((uint16_t *) &tuple[15]) = uh->uh_sport; break; default: memset(&tuple[13], 0, 4); } hash = jenkins_hash(tuple, 17, HASHINIT) % fcount; return hash; } /* * Enqueue a packet into an appropriate queue according to * FQ-CoDe; algorithm. */ static int fq_pie_enqueue(struct dn_sch_inst *_si, struct dn_queue *_q, struct mbuf *m) { struct fq_pie_si *si; struct fq_pie_schk *schk; struct dn_sch_fq_pie_parms *param; struct dn_queue *mainq; struct fq_pie_flow *flows; int idx, drop, i, maxidx; mainq = (struct dn_queue *)(_si + 1); si = (struct fq_pie_si *)_si; flows = si->si_extra->flows; schk = (struct fq_pie_schk *)(si->_si.sched+1); param = &schk->cfg; /* classify a packet to queue number*/ idx = fq_pie_classify_flow(m, param->flows_cnt, si); /* enqueue packet into appropriate queue using PIE AQM. * Note: 'pie_enqueue' function returns 1 only when it unable to * add timestamp to packet (no limit check)*/ drop = pie_enqueue(&flows[idx], m, si); /* pie unable to timestamp a packet */ if (drop) return 1; /* If the flow (sub-queue) is not active ,then add it to tail of * new flows list, initialize and activate it. */ if (!flows[idx].active) { STAILQ_INSERT_TAIL(&si->newflows, &flows[idx], flowchain); flows[idx].deficit = param->quantum; fq_activate_pie(&flows[idx]); flows[idx].active = 1; } /* check the limit for all queues and remove a packet from the * largest one */ if (mainq->ni.length > schk->cfg.limit) { /* find first active flow */ for (maxidx = 0; maxidx < schk->cfg.flows_cnt; maxidx++) if (flows[maxidx].active) break; if (maxidx < schk->cfg.flows_cnt) { /* find the largest sub- queue */ for (i = maxidx + 1; i < schk->cfg.flows_cnt; i++) if (flows[i].active && flows[i].stats.length > flows[maxidx].stats.length) maxidx = i; pie_drop_head(&flows[maxidx], si); drop = 1; } } return drop; } /* * Dequeue a packet from an appropriate queue according to * FQ-CoDel algorithm. */ static struct mbuf * fq_pie_dequeue(struct dn_sch_inst *_si) { struct fq_pie_si *si; struct fq_pie_schk *schk; struct dn_sch_fq_pie_parms *param; struct fq_pie_flow *f; struct mbuf *mbuf; struct fq_pie_list *fq_pie_flowlist; si = (struct fq_pie_si *)_si; schk = (struct fq_pie_schk *)(si->_si.sched+1); param = &schk->cfg; do { /* select a list to start with */ if (STAILQ_EMPTY(&si->newflows)) fq_pie_flowlist = &si->oldflows; else fq_pie_flowlist = &si->newflows; /* Both new and old queue lists are empty, return NULL */ if (STAILQ_EMPTY(fq_pie_flowlist)) return NULL; f = STAILQ_FIRST(fq_pie_flowlist); while (f != NULL) { /* if there is no flow(sub-queue) deficit, increase deficit * by quantum, move the flow to the tail of old flows list * and try another flow. * Otherwise, the flow will be used for dequeue. */ if (f->deficit < 0) { f->deficit += param->quantum; STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain); STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain); } else break; f = STAILQ_FIRST(fq_pie_flowlist); } /* the new flows list is empty, try old flows list */ if (STAILQ_EMPTY(fq_pie_flowlist)) continue; /* Dequeue a packet from the selected flow */ mbuf = pie_dequeue(f, si); /* pie did not return a packet */ if (!mbuf) { /* If the selected flow belongs to new flows list, then move * it to the tail of old flows list. Otherwise, deactivate it and * remove it from the old list and */ if (fq_pie_flowlist == &si->newflows) { STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain); STAILQ_INSERT_TAIL(&si->oldflows, f, flowchain); } else { f->active = 0; fq_deactivate_pie(&f->pst); STAILQ_REMOVE_HEAD(fq_pie_flowlist, flowchain); } /* start again */ continue; } /* we have a packet to return, * update flow deficit and return the packet*/ f->deficit -= mbuf->m_pkthdr.len; return mbuf; } while (1); /* unreachable point */ return NULL; } /* * Initialize fq_pie scheduler instance. * also, allocate memory for flows array. */ static int fq_pie_new_sched(struct dn_sch_inst *_si) { struct fq_pie_si *si; struct dn_queue *q; struct fq_pie_schk *schk; struct fq_pie_flow *flows; int i; si = (struct fq_pie_si *)_si; schk = (struct fq_pie_schk *)(_si->sched+1); if(si->si_extra) { D("si already configured!"); return 0; } /* init the main queue */ q = &si->main_q; set_oid(&q->ni.oid, DN_QUEUE, sizeof(*q)); q->_si = _si; q->fs = _si->sched->fs; /* allocate memory for scheduler instance extra vars */ si->si_extra = malloc(sizeof(struct fq_pie_si_extra), M_DUMMYNET, M_NOWAIT | M_ZERO); if (si->si_extra == NULL) { D("cannot allocate memory for fq_pie si extra vars"); return ENOMEM ; } /* allocate memory for flows array */ si->si_extra->flows = malloc(schk->cfg.flows_cnt * sizeof(struct fq_pie_flow), M_DUMMYNET, M_NOWAIT | M_ZERO); flows = si->si_extra->flows; if (flows == NULL) { free(si->si_extra, M_DUMMYNET); si->si_extra = NULL; D("cannot allocate memory for fq_pie flows"); return ENOMEM ; } /* init perturbation for this si */ si->perturbation = random(); si->si_extra->nr_active_q = 0; /* init the old and new flows lists */ STAILQ_INIT(&si->newflows); STAILQ_INIT(&si->oldflows); /* init the flows (sub-queues) */ for (i = 0; i < schk->cfg.flows_cnt; i++) { flows[i].pst.parms = &schk->cfg.pcfg; flows[i].psi_extra = si->si_extra; pie_init(&flows[i], schk); } fq_pie_desc.ref_count++; return 0; } /* * Free fq_pie scheduler instance. */ static int fq_pie_free_sched(struct dn_sch_inst *_si) { struct fq_pie_si *si; struct fq_pie_schk *schk; struct fq_pie_flow *flows; int i; si = (struct fq_pie_si *)_si; schk = (struct fq_pie_schk *)(_si->sched+1); flows = si->si_extra->flows; for (i = 0; i < schk->cfg.flows_cnt; i++) { pie_cleanup(&flows[i]); } si->si_extra = NULL; return 0; } /* * Configure FQ-PIE scheduler. * the configurations for the scheduler is passed fromipfw userland. */ static int fq_pie_config(struct dn_schk *_schk) { struct fq_pie_schk *schk; struct dn_extra_parms *ep; struct dn_sch_fq_pie_parms *fqp_cfg; schk = (struct fq_pie_schk *)(_schk+1); ep = (struct dn_extra_parms *) _schk->cfg; /* par array contains fq_pie configuration as follow * PIE: 0- qdelay_ref,1- tupdate, 2- max_burst * 3- max_ecnth, 4- alpha, 5- beta, 6- flags * FQ_PIE: 7- quantum, 8- limit, 9- flows */ if (ep && ep->oid.len ==sizeof(*ep) && ep->oid.subtype == DN_SCH_PARAMS) { fqp_cfg = &schk->cfg; if (ep->par[0] < 0) fqp_cfg->pcfg.qdelay_ref = fq_pie_sysctl.pcfg.qdelay_ref; else fqp_cfg->pcfg.qdelay_ref = ep->par[0]; if (ep->par[1] < 0) fqp_cfg->pcfg.tupdate = fq_pie_sysctl.pcfg.tupdate; else fqp_cfg->pcfg.tupdate = ep->par[1]; if (ep->par[2] < 0) fqp_cfg->pcfg.max_burst = fq_pie_sysctl.pcfg.max_burst; else fqp_cfg->pcfg.max_burst = ep->par[2]; if (ep->par[3] < 0) fqp_cfg->pcfg.max_ecnth = fq_pie_sysctl.pcfg.max_ecnth; else fqp_cfg->pcfg.max_ecnth = ep->par[3]; if (ep->par[4] < 0) fqp_cfg->pcfg.alpha = fq_pie_sysctl.pcfg.alpha; else fqp_cfg->pcfg.alpha = ep->par[4]; if (ep->par[5] < 0) fqp_cfg->pcfg.beta = fq_pie_sysctl.pcfg.beta; else fqp_cfg->pcfg.beta = ep->par[5]; if (ep->par[6] < 0) fqp_cfg->pcfg.flags = 0; else fqp_cfg->pcfg.flags = ep->par[6]; /* FQ configurations */ if (ep->par[7] < 0) fqp_cfg->quantum = fq_pie_sysctl.quantum; else fqp_cfg->quantum = ep->par[7]; if (ep->par[8] < 0) fqp_cfg->limit = fq_pie_sysctl.limit; else fqp_cfg->limit = ep->par[8]; if (ep->par[9] < 0) fqp_cfg->flows_cnt = fq_pie_sysctl.flows_cnt; else fqp_cfg->flows_cnt = ep->par[9]; /* Bound the configurations */ fqp_cfg->pcfg.qdelay_ref = BOUND_VAR(fqp_cfg->pcfg.qdelay_ref, 1, 5 * AQM_TIME_1S); fqp_cfg->pcfg.tupdate = BOUND_VAR(fqp_cfg->pcfg.tupdate, 1, 5 * AQM_TIME_1S); fqp_cfg->pcfg.max_burst = BOUND_VAR(fqp_cfg->pcfg.max_burst, 0, 5 * AQM_TIME_1S); fqp_cfg->pcfg.max_ecnth = BOUND_VAR(fqp_cfg->pcfg.max_ecnth, 0, PIE_SCALE); fqp_cfg->pcfg.alpha = BOUND_VAR(fqp_cfg->pcfg.alpha, 0, 7 * PIE_SCALE); fqp_cfg->pcfg.beta = BOUND_VAR(fqp_cfg->pcfg.beta, 0, 7 * PIE_SCALE); fqp_cfg->quantum = BOUND_VAR(fqp_cfg->quantum,1,9000); fqp_cfg->limit= BOUND_VAR(fqp_cfg->limit,1,20480); fqp_cfg->flows_cnt= BOUND_VAR(fqp_cfg->flows_cnt,1,65536); } else { D("Wrong parameters for fq_pie scheduler"); return 1; } return 0; } /* * Return FQ-PIE scheduler configurations * the configurations for the scheduler is passed to userland. */ static int fq_pie_getconfig (struct dn_schk *_schk, struct dn_extra_parms *ep) { struct fq_pie_schk *schk = (struct fq_pie_schk *)(_schk+1); struct dn_sch_fq_pie_parms *fqp_cfg; fqp_cfg = &schk->cfg; strcpy(ep->name, fq_pie_desc.name); ep->par[0] = fqp_cfg->pcfg.qdelay_ref; ep->par[1] = fqp_cfg->pcfg.tupdate; ep->par[2] = fqp_cfg->pcfg.max_burst; ep->par[3] = fqp_cfg->pcfg.max_ecnth; ep->par[4] = fqp_cfg->pcfg.alpha; ep->par[5] = fqp_cfg->pcfg.beta; ep->par[6] = fqp_cfg->pcfg.flags; ep->par[7] = fqp_cfg->quantum; ep->par[8] = fqp_cfg->limit; ep->par[9] = fqp_cfg->flows_cnt; return 0; } /* * FQ-PIE scheduler descriptor * contains the type of the scheduler, the name, the size of extra * data structures, and function pointers. */ static struct dn_alg fq_pie_desc = { _SI( .type = ) DN_SCHED_FQ_PIE, _SI( .name = ) "FQ_PIE", _SI( .flags = ) 0, _SI( .schk_datalen = ) sizeof(struct fq_pie_schk), _SI( .si_datalen = ) sizeof(struct fq_pie_si) - sizeof(struct dn_sch_inst), _SI( .q_datalen = ) 0, _SI( .enqueue = ) fq_pie_enqueue, _SI( .dequeue = ) fq_pie_dequeue, _SI( .config = ) fq_pie_config, /* new sched i.e. sched X config ...*/ _SI( .destroy = ) NULL, /*sched x delete */ _SI( .new_sched = ) fq_pie_new_sched, /* new schd instance */ _SI( .free_sched = ) fq_pie_free_sched, /* delete schd instance */ _SI( .new_fsk = ) NULL, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) NULL, _SI( .free_queue = ) NULL, _SI( .getconfig = ) fq_pie_getconfig, _SI( .ref_count = ) 0 }; DECLARE_DNSCHED_MODULE(dn_fq_pie, &fq_pie_desc); Index: stable/11/sys/netpfil/ipfw/dn_sched_prio.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_prio.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_prio.c (revision 325730) @@ -1,235 +1,238 @@ /* * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * $FreeBSD$ */ #ifdef _KERNEL #include #include #include #include +#include #include #include +#include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include +#include #include #include #ifdef NEW_AQM #include #endif #include #else #include #endif #define DN_SCHED_PRIO 5 //XXX #if !defined(_KERNEL) || !defined(__linux__) #define test_bit(ix, pData) ((*pData) & (1<<(ix))) #define __set_bit(ix, pData) (*pData) |= (1<<(ix)) #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix)) #endif #ifdef __MIPSEL__ #define __clear_bit(ix, pData) (*pData) &= ~(1<<(ix)) #endif /* Size of the array of queues pointers. */ #define BITMAP_T unsigned long #define MAXPRIO (sizeof(BITMAP_T) * 8) /* * The scheduler instance contains an array of pointers to queues, * one for each priority, and a bitmap listing backlogged queues. */ struct prio_si { BITMAP_T bitmap; /* array bitmap */ struct dn_queue *q_array[MAXPRIO]; /* Array of queues pointers */ }; /* * If a queue with the same priority is already backlogged, use * that one instead of the queue passed as argument. */ static int prio_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) { struct prio_si *si = (struct prio_si *)(_si + 1); int prio = q->fs->fs.par[0]; if (test_bit(prio, &si->bitmap) == 0) { /* No queue with this priority, insert */ __set_bit(prio, &si->bitmap); si->q_array[prio] = q; } else { /* use the existing queue */ q = si->q_array[prio]; } if (dn_enqueue(q, m, 0)) return 1; return 0; } /* * Packets are dequeued only from the highest priority queue. * The function ffs() return the lowest bit in the bitmap that rapresent * the array index (-1) which contains the pointer to the highest priority * queue. * After the dequeue, if this queue become empty, it is index is removed * from the bitmap. * Scheduler is idle if the bitmap is empty * * NOTE: highest priority is 0, lowest is sched->max_prio_q */ static struct mbuf * prio_dequeue(struct dn_sch_inst *_si) { struct prio_si *si = (struct prio_si *)(_si + 1); struct mbuf *m; struct dn_queue *q; int prio; if (si->bitmap == 0) /* scheduler idle */ return NULL; prio = ffs(si->bitmap) - 1; /* Take the highest priority queue in the scheduler */ q = si->q_array[prio]; // assert(q) m = dn_dequeue(q); if (q->mq.head == NULL) { /* Queue is now empty, remove from scheduler * and mark it */ si->q_array[prio] = NULL; __clear_bit(prio, &si->bitmap); } return m; } static int prio_new_sched(struct dn_sch_inst *_si) { struct prio_si *si = (struct prio_si *)(_si + 1); bzero(si->q_array, sizeof(si->q_array)); si->bitmap = 0; return 0; } static int prio_new_fsk(struct dn_fsk *fs) { /* Check if the prioritiy is between 0 and MAXPRIO-1 */ ipdn_bound_var(&fs->fs.par[0], 0, 0, MAXPRIO - 1, "PRIO priority"); return 0; } static int prio_new_queue(struct dn_queue *q) { struct prio_si *si = (struct prio_si *)(q->_si + 1); int prio = q->fs->fs.par[0]; struct dn_queue *oldq; q->ni.oid.subtype = DN_SCHED_PRIO; if (q->mq.head == NULL) return 0; /* Queue already full, must insert in the scheduler or append * mbufs to existing queue. This partly duplicates prio_enqueue */ if (test_bit(prio, &si->bitmap) == 0) { /* No queue with this priority, insert */ __set_bit(prio, &si->bitmap); si->q_array[prio] = q; } else if ( (oldq = si->q_array[prio]) != q) { /* must append to the existing queue. * can simply append q->mq.head to q2->... * and add the counters to those of q2 */ oldq->mq.tail->m_nextpkt = q->mq.head; oldq->mq.tail = q->mq.tail; oldq->ni.length += q->ni.length; q->ni.length = 0; oldq->ni.len_bytes += q->ni.len_bytes; q->ni.len_bytes = 0; q->mq.tail = q->mq.head = NULL; } return 0; } static int prio_free_queue(struct dn_queue *q) { int prio = q->fs->fs.par[0]; struct prio_si *si = (struct prio_si *)(q->_si + 1); if (si->q_array[prio] == q) { si->q_array[prio] = NULL; __clear_bit(prio, &si->bitmap); } return 0; } static struct dn_alg prio_desc = { _SI( .type = ) DN_SCHED_PRIO, _SI( .name = ) "PRIO", _SI( .flags = ) DN_MULTIQUEUE, /* we need extra space in the si and the queue */ _SI( .schk_datalen = ) 0, _SI( .si_datalen = ) sizeof(struct prio_si), _SI( .q_datalen = ) 0, _SI( .enqueue = ) prio_enqueue, _SI( .dequeue = ) prio_dequeue, _SI( .config = ) NULL, _SI( .destroy = ) NULL, _SI( .new_sched = ) prio_new_sched, _SI( .free_sched = ) NULL, _SI( .new_fsk = ) prio_new_fsk, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) prio_new_queue, _SI( .free_queue = ) prio_free_queue, #ifdef NEW_AQM _SI( .getconfig = ) NULL, #endif }; DECLARE_DNSCHED_MODULE(dn_prio, &prio_desc); Index: stable/11/sys/netpfil/ipfw/dn_sched_qfq.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_qfq.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_qfq.c (revision 325730) @@ -1,883 +1,886 @@ /* * Copyright (c) 2010 Fabio Checconi, Luigi Rizzo, Paolo Valente * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * $FreeBSD$ */ #ifdef _KERNEL #include #include #include #include +#include #include #include +#include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include +#include #include #include #ifdef NEW_AQM #include #endif #include #else #include #endif #ifdef QFQ_DEBUG #define _P64 unsigned long long /* cast for printing uint64_t */ struct qfq_sched; static void dump_sched(struct qfq_sched *q, const char *msg); #define NO(x) x #else #define NO(x) #endif #define DN_SCHED_QFQ 4 // XXX Where? typedef unsigned long bitmap; /* * bitmaps ops are critical. Some linux versions have __fls * and the bitmap ops. Some machines have ffs * NOTE: fls() returns 1 for the least significant bit, * __fls() returns 0 for the same case. * We use the base-0 version __fls() to match the description in * the ToN QFQ paper */ #if defined(_WIN32) || (defined(__MIPSEL__) && defined(LINUX_24)) int fls(unsigned int n) { int i = 0; for (i = 0; n > 0; n >>= 1, i++) ; return i; } #endif #if !defined(_KERNEL) || defined( __FreeBSD__ ) || defined(_WIN32) || (defined(__MIPSEL__) && defined(LINUX_24)) static inline unsigned long __fls(unsigned long word) { return fls(word) - 1; } #endif #if !defined(_KERNEL) || !defined(__linux__) #ifdef QFQ_DEBUG static int test_bit(int ix, bitmap *p) { if (ix < 0 || ix > 31) D("bad index %d", ix); return *p & (1< 31) D("bad index %d", ix); *p |= (1< 31) D("bad index %d", ix); *p &= ~(1<index = 0 *.__grp->slot_shift where MIN_SLOT_SHIFT is derived by difference from the others. The max group index corresponds to Lmax/w_min, where Lmax=1<group mapping. Class weights are * in the range [1, QFQ_MAX_WEIGHT], we to map each class i to the * group with the smallest index that can support the L_i / r_i * configured for the class. * * grp->index is the index of the group; and grp->slot_shift * is the shift for the corresponding (scaled) sigma_i. * * When computing the group index, we do (len< 0; } /* Round a precise timestamp to its slotted value. */ static inline uint64_t qfq_round_down(uint64_t ts, unsigned int shift) { return ts & ~((1ULL << shift) - 1); } /* return the pointer to the group with lowest index in the bitmap */ static inline struct qfq_group *qfq_ffs(struct qfq_sched *q, unsigned long bitmap) { int index = ffs(bitmap) - 1; // zero-based return &q->groups[index]; } /* * Calculate a flow index, given its weight and maximum packet length. * index = log_2(maxlen/weight) but we need to apply the scaling. * This is used only once at flow creation. */ static int qfq_calc_index(uint32_t inv_w, unsigned int maxlen) { uint64_t slot_size = (uint64_t)maxlen *inv_w; unsigned long size_map; int index = 0; size_map = (unsigned long)(slot_size >> QFQ_MIN_SLOT_SHIFT); if (!size_map) goto out; index = __fls(size_map) + 1; // basically a log_2() index -= !(slot_size - (1ULL << (index + QFQ_MIN_SLOT_SHIFT - 1))); if (index < 0) index = 0; out: ND("W = %d, L = %d, I = %d\n", ONE_FP/inv_w, maxlen, index); return index; } /*---- end support functions ----*/ /*-------- API calls --------------------------------*/ /* * Validate and copy parameters from flowset. */ static int qfq_new_queue(struct dn_queue *_q) { struct qfq_sched *q = (struct qfq_sched *)(_q->_si + 1); struct qfq_class *cl = (struct qfq_class *)_q; int i; uint32_t w; /* approximated weight */ /* import parameters from the flowset. They should be correct * already. */ w = _q->fs->fs.par[0]; cl->lmax = _q->fs->fs.par[1]; if (!w || w > QFQ_MAX_WEIGHT) { w = 1; D("rounding weight to 1"); } cl->inv_w = ONE_FP/w; w = ONE_FP/cl->inv_w; if (q->wsum + w > QFQ_MAX_WSUM) return EINVAL; i = qfq_calc_index(cl->inv_w, cl->lmax); cl->grp = &q->groups[i]; q->wsum += w; q->iwsum = ONE_FP / q->wsum; /* XXX note theory */ // XXX cl->S = q->V; ? return 0; } /* remove an empty queue */ static int qfq_free_queue(struct dn_queue *_q) { struct qfq_sched *q = (struct qfq_sched *)(_q->_si + 1); struct qfq_class *cl = (struct qfq_class *)_q; if (cl->inv_w) { q->wsum -= ONE_FP/cl->inv_w; if (q->wsum != 0) q->iwsum = ONE_FP / q->wsum; cl->inv_w = 0; /* reset weight to avoid run twice */ } return 0; } /* Calculate a mask to mimic what would be ffs_from(). */ static inline unsigned long mask_from(unsigned long bitmap, int from) { return bitmap & ~((1UL << from) - 1); } /* * The state computation relies on ER=0, IR=1, EB=2, IB=3 * First compute eligibility comparing grp->S, q->V, * then check if someone is blocking us and possibly add EB */ static inline unsigned int qfq_calc_state(struct qfq_sched *q, struct qfq_group *grp) { /* if S > V we are not eligible */ unsigned int state = qfq_gt(grp->S, q->V); unsigned long mask = mask_from(q->bitmaps[ER], grp->index); struct qfq_group *next; if (mask) { next = qfq_ffs(q, mask); if (qfq_gt(grp->F, next->F)) state |= EB; } return state; } /* * In principle * q->bitmaps[dst] |= q->bitmaps[src] & mask; * q->bitmaps[src] &= ~mask; * but we should make sure that src != dst */ static inline void qfq_move_groups(struct qfq_sched *q, unsigned long mask, int src, int dst) { q->bitmaps[dst] |= q->bitmaps[src] & mask; q->bitmaps[src] &= ~mask; } static inline void qfq_unblock_groups(struct qfq_sched *q, int index, uint64_t old_finish) { unsigned long mask = mask_from(q->bitmaps[ER], index + 1); struct qfq_group *next; if (mask) { next = qfq_ffs(q, mask); if (!qfq_gt(next->F, old_finish)) return; } mask = (1UL << index) - 1; qfq_move_groups(q, mask, EB, ER); qfq_move_groups(q, mask, IB, IR); } /* * perhaps * old_V ^= q->V; old_V >>= QFQ_MIN_SLOT_SHIFT; if (old_V) { ... } * */ static inline void qfq_make_eligible(struct qfq_sched *q, uint64_t old_V) { unsigned long mask, vslot, old_vslot; vslot = q->V >> QFQ_MIN_SLOT_SHIFT; old_vslot = old_V >> QFQ_MIN_SLOT_SHIFT; if (vslot != old_vslot) { /* must be 2ULL, see ToN QFQ article fig.5, we use base-0 fls */ mask = (2ULL << (__fls(vslot ^ old_vslot))) - 1; qfq_move_groups(q, mask, IR, ER); qfq_move_groups(q, mask, IB, EB); } } /* * XXX we should make sure that slot becomes less than 32. * This is guaranteed by the input values. * roundedS is always cl->S rounded on grp->slot_shift bits. */ static inline void qfq_slot_insert(struct qfq_group *grp, struct qfq_class *cl, uint64_t roundedS) { uint64_t slot = (roundedS - grp->S) >> grp->slot_shift; unsigned int i = (grp->front + slot) % QFQ_MAX_SLOTS; cl->next = grp->slots[i]; grp->slots[i] = cl; __set_bit(slot, &grp->full_slots); } /* * remove the entry from the slot */ static inline void qfq_front_slot_remove(struct qfq_group *grp) { struct qfq_class **h = &grp->slots[grp->front]; *h = (*h)->next; if (!*h) __clear_bit(0, &grp->full_slots); } /* * Returns the first full queue in a group. As a side effect, * adjust the bucket list so the first non-empty bucket is at * position 0 in full_slots. */ static inline struct qfq_class * qfq_slot_scan(struct qfq_group *grp) { int i; ND("grp %d full %x", grp->index, grp->full_slots); if (!grp->full_slots) return NULL; i = ffs(grp->full_slots) - 1; // zero-based if (i > 0) { grp->front = (grp->front + i) % QFQ_MAX_SLOTS; grp->full_slots >>= i; } return grp->slots[grp->front]; } /* * adjust the bucket list. When the start time of a group decreases, * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to * move the objects. The mask of occupied slots must be shifted * because we use ffs() to find the first non-empty slot. * This covers decreases in the group's start time, but what about * increases of the start time ? * Here too we should make sure that i is less than 32 */ static inline void qfq_slot_rotate(struct qfq_sched *q, struct qfq_group *grp, uint64_t roundedS) { unsigned int i = (grp->S - roundedS) >> grp->slot_shift; (void)q; grp->full_slots <<= i; grp->front = (grp->front - i) % QFQ_MAX_SLOTS; } static inline void qfq_update_eligible(struct qfq_sched *q, uint64_t old_V) { bitmap ineligible; ineligible = q->bitmaps[IR] | q->bitmaps[IB]; if (ineligible) { if (!q->bitmaps[ER]) { struct qfq_group *grp; grp = qfq_ffs(q, ineligible); if (qfq_gt(grp->S, q->V)) q->V = grp->S; } qfq_make_eligible(q, old_V); } } /* * Updates the class, returns true if also the group needs to be updated. */ static inline int qfq_update_class(struct qfq_sched *q, struct qfq_group *grp, struct qfq_class *cl) { (void)q; cl->S = cl->F; if (cl->_q.mq.head == NULL) { qfq_front_slot_remove(grp); } else { unsigned int len; uint64_t roundedS; len = cl->_q.mq.head->m_pkthdr.len; cl->F = cl->S + (uint64_t)len * cl->inv_w; roundedS = qfq_round_down(cl->S, grp->slot_shift); if (roundedS == grp->S) return 0; qfq_front_slot_remove(grp); qfq_slot_insert(grp, cl, roundedS); } return 1; } static struct mbuf * qfq_dequeue(struct dn_sch_inst *si) { struct qfq_sched *q = (struct qfq_sched *)(si + 1); struct qfq_group *grp; struct qfq_class *cl; struct mbuf *m; uint64_t old_V; NO(q->loops++;) if (!q->bitmaps[ER]) { NO(if (q->queued) dump_sched(q, "start dequeue");) return NULL; } grp = qfq_ffs(q, q->bitmaps[ER]); cl = grp->slots[grp->front]; /* extract from the first bucket in the bucket list */ m = dn_dequeue(&cl->_q); if (!m) { D("BUG/* non-workconserving leaf */"); return NULL; } NO(q->queued--;) old_V = q->V; q->V += (uint64_t)m->m_pkthdr.len * q->iwsum; ND("m is %p F 0x%llx V now 0x%llx", m, cl->F, q->V); if (qfq_update_class(q, grp, cl)) { uint64_t old_F = grp->F; cl = qfq_slot_scan(grp); if (!cl) { /* group gone, remove from ER */ __clear_bit(grp->index, &q->bitmaps[ER]); // grp->S = grp->F + 1; // XXX debugging only } else { uint64_t roundedS = qfq_round_down(cl->S, grp->slot_shift); unsigned int s; if (grp->S == roundedS) goto skip_unblock; grp->S = roundedS; grp->F = roundedS + (2ULL << grp->slot_shift); /* remove from ER and put in the new set */ __clear_bit(grp->index, &q->bitmaps[ER]); s = qfq_calc_state(q, grp); __set_bit(grp->index, &q->bitmaps[s]); } /* we need to unblock even if the group has gone away */ qfq_unblock_groups(q, grp->index, old_F); } skip_unblock: qfq_update_eligible(q, old_V); NO(if (!q->bitmaps[ER] && q->queued) dump_sched(q, "end dequeue");) return m; } /* * Assign a reasonable start time for a new flow k in group i. * Admissible values for \hat(F) are multiples of \sigma_i * no greater than V+\sigma_i . Larger values mean that * we had a wraparound so we consider the timestamp to be stale. * * If F is not stale and F >= V then we set S = F. * Otherwise we should assign S = V, but this may violate * the ordering in ER. So, if we have groups in ER, set S to * the F_j of the first group j which would be blocking us. * We are guaranteed not to move S backward because * otherwise our group i would still be blocked. */ static inline void qfq_update_start(struct qfq_sched *q, struct qfq_class *cl) { unsigned long mask; uint64_t limit, roundedF; int slot_shift = cl->grp->slot_shift; roundedF = qfq_round_down(cl->F, slot_shift); limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift); if (!qfq_gt(cl->F, q->V) || qfq_gt(roundedF, limit)) { /* timestamp was stale */ mask = mask_from(q->bitmaps[ER], cl->grp->index); if (mask) { struct qfq_group *next = qfq_ffs(q, mask); if (qfq_gt(roundedF, next->F)) { /* from pv 71261956973ba9e0637848a5adb4a5819b4bae83 */ if (qfq_gt(limit, next->F)) cl->S = next->F; else /* preserve timestamp correctness */ cl->S = limit; return; } } cl->S = q->V; } else { /* timestamp is not stale */ cl->S = cl->F; } } static int qfq_enqueue(struct dn_sch_inst *si, struct dn_queue *_q, struct mbuf *m) { struct qfq_sched *q = (struct qfq_sched *)(si + 1); struct qfq_group *grp; struct qfq_class *cl = (struct qfq_class *)_q; uint64_t roundedS; int s; NO(q->loops++;) DX(4, "len %d flow %p inv_w 0x%x grp %d", m->m_pkthdr.len, _q, cl->inv_w, cl->grp->index); /* XXX verify that the packet obeys the parameters */ if (m != _q->mq.head) { if (dn_enqueue(_q, m, 0)) /* packet was dropped */ return 1; NO(q->queued++;) if (m != _q->mq.head) return 0; } /* If reach this point, queue q was idle */ grp = cl->grp; qfq_update_start(q, cl); /* adjust start time */ /* compute new finish time and rounded start. */ cl->F = cl->S + (uint64_t)(m->m_pkthdr.len) * cl->inv_w; roundedS = qfq_round_down(cl->S, grp->slot_shift); /* * insert cl in the correct bucket. * If cl->S >= grp->S we don't need to adjust the * bucket list and simply go to the insertion phase. * Otherwise grp->S is decreasing, we must make room * in the bucket list, and also recompute the group state. * Finally, if there were no flows in this group and nobody * was in ER make sure to adjust V. */ if (grp->full_slots) { if (!qfq_gt(grp->S, cl->S)) goto skip_update; /* create a slot for this cl->S */ qfq_slot_rotate(q, grp, roundedS); /* group was surely ineligible, remove */ __clear_bit(grp->index, &q->bitmaps[IR]); __clear_bit(grp->index, &q->bitmaps[IB]); } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V)) q->V = roundedS; grp->S = roundedS; grp->F = roundedS + (2ULL << grp->slot_shift); // i.e. 2\sigma_i s = qfq_calc_state(q, grp); __set_bit(grp->index, &q->bitmaps[s]); ND("new state %d 0x%x", s, q->bitmaps[s]); ND("S %llx F %llx V %llx", cl->S, cl->F, q->V); skip_update: qfq_slot_insert(grp, cl, roundedS); return 0; } #if 0 static inline void qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp, struct qfq_class *cl, struct qfq_class **pprev) { unsigned int i, offset; uint64_t roundedS; roundedS = qfq_round_down(cl->S, grp->slot_shift); offset = (roundedS - grp->S) >> grp->slot_shift; i = (grp->front + offset) % QFQ_MAX_SLOTS; #ifdef notyet if (!pprev) { pprev = &grp->slots[i]; while (*pprev && *pprev != cl) pprev = &(*pprev)->next; } #endif *pprev = cl->next; if (!grp->slots[i]) __clear_bit(offset, &grp->full_slots); } /* * called to forcibly destroy a queue. * If the queue is not in the front bucket, or if it has * other queues in the front bucket, we can simply remove * the queue with no other side effects. * Otherwise we must propagate the event up. * XXX description to be completed. */ static void qfq_deactivate_class(struct qfq_sched *q, struct qfq_class *cl, struct qfq_class **pprev) { struct qfq_group *grp = &q->groups[cl->index]; unsigned long mask; uint64_t roundedS; int s; cl->F = cl->S; // not needed if the class goes away. qfq_slot_remove(q, grp, cl, pprev); if (!grp->full_slots) { /* nothing left in the group, remove from all sets. * Do ER last because if we were blocking other groups * we must unblock them. */ __clear_bit(grp->index, &q->bitmaps[IR]); __clear_bit(grp->index, &q->bitmaps[EB]); __clear_bit(grp->index, &q->bitmaps[IB]); if (test_bit(grp->index, &q->bitmaps[ER]) && !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) { mask = q->bitmaps[ER] & ((1UL << grp->index) - 1); if (mask) mask = ~((1UL << __fls(mask)) - 1); else mask = ~0UL; qfq_move_groups(q, mask, EB, ER); qfq_move_groups(q, mask, IB, IR); } __clear_bit(grp->index, &q->bitmaps[ER]); } else if (!grp->slots[grp->front]) { cl = qfq_slot_scan(grp); roundedS = qfq_round_down(cl->S, grp->slot_shift); if (grp->S != roundedS) { __clear_bit(grp->index, &q->bitmaps[ER]); __clear_bit(grp->index, &q->bitmaps[IR]); __clear_bit(grp->index, &q->bitmaps[EB]); __clear_bit(grp->index, &q->bitmaps[IB]); grp->S = roundedS; grp->F = roundedS + (2ULL << grp->slot_shift); s = qfq_calc_state(q, grp); __set_bit(grp->index, &q->bitmaps[s]); } } qfq_update_eligible(q, q->V); } #endif static int qfq_new_fsk(struct dn_fsk *f) { ipdn_bound_var(&f->fs.par[0], 1, 1, QFQ_MAX_WEIGHT, "qfq weight"); ipdn_bound_var(&f->fs.par[1], 1500, 1, 2000, "qfq maxlen"); ND("weight %d len %d\n", f->fs.par[0], f->fs.par[1]); return 0; } /* * initialize a new scheduler instance */ static int qfq_new_sched(struct dn_sch_inst *si) { struct qfq_sched *q = (struct qfq_sched *)(si + 1); struct qfq_group *grp; int i; for (i = 0; i <= QFQ_MAX_INDEX; i++) { grp = &q->groups[i]; grp->index = i; grp->slot_shift = QFQ_MTU_SHIFT + FRAC_BITS - (QFQ_MAX_INDEX - i); } return 0; } /* * QFQ scheduler descriptor */ static struct dn_alg qfq_desc = { _SI( .type = ) DN_SCHED_QFQ, _SI( .name = ) "QFQ", _SI( .flags = ) DN_MULTIQUEUE, _SI( .schk_datalen = ) 0, _SI( .si_datalen = ) sizeof(struct qfq_sched), _SI( .q_datalen = ) sizeof(struct qfq_class) - sizeof(struct dn_queue), _SI( .enqueue = ) qfq_enqueue, _SI( .dequeue = ) qfq_dequeue, _SI( .config = ) NULL, _SI( .destroy = ) NULL, _SI( .new_sched = ) qfq_new_sched, _SI( .free_sched = ) NULL, _SI( .new_fsk = ) qfq_new_fsk, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) qfq_new_queue, _SI( .free_queue = ) qfq_free_queue, #ifdef NEW_AQM _SI( .getconfig = ) NULL, #endif }; DECLARE_DNSCHED_MODULE(dn_qfq, &qfq_desc); #ifdef QFQ_DEBUG static void dump_groups(struct qfq_sched *q, uint32_t mask) { int i, j; for (i = 0; i < QFQ_MAX_INDEX + 1; i++) { struct qfq_group *g = &q->groups[i]; if (0 == (mask & (1<slots[j]) D(" bucket %d %p", j, g->slots[j]); } D("full_slots 0x%llx", (_P64)g->full_slots); D(" %2d S 0x%20llx F 0x%llx %c", i, (_P64)g->S, (_P64)g->F, mask & (1<loops, q->queued, (_P64)q->V); D(" ER 0x%08x", (unsigned)q->bitmaps[ER]); D(" EB 0x%08x", (unsigned)q->bitmaps[EB]); D(" IR 0x%08x", (unsigned)q->bitmaps[IR]); D(" IB 0x%08x", (unsigned)q->bitmaps[IB]); dump_groups(q, 0xffffffff); }; #endif /* QFQ_DEBUG */ Index: stable/11/sys/netpfil/ipfw/dn_sched_rr.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_rr.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_rr.c (revision 325730) @@ -1,321 +1,324 @@ /* * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * $FreeBSD$ */ #ifdef _KERNEL #include #include #include #include +#include #include #include +#include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include +#include #include #include #ifdef NEW_AQM #include #endif #include #else #include #endif #define DN_SCHED_RR 3 // XXX Where? struct rr_queue { struct dn_queue q; /* Standard queue */ int status; /* 1: queue is in the list */ uint32_t credit; /* max bytes we can transmit */ uint32_t quantum; /* quantum * weight */ struct rr_queue *qnext; /* */ }; /* struct rr_schk contains global config parameters * and is right after dn_schk */ struct rr_schk { uint32_t min_q; /* Min quantum */ uint32_t max_q; /* Max quantum */ uint32_t q_bytes; /* default quantum in bytes */ }; /* per-instance round robin list, right after dn_sch_inst */ struct rr_si { struct rr_queue *head, *tail; /* Pointer to current queue */ }; /* Append a queue to the rr list */ static inline void rr_append(struct rr_queue *q, struct rr_si *si) { q->status = 1; /* mark as in-rr_list */ q->credit = q->quantum; /* initialize credit */ /* append to the tail */ if (si->head == NULL) si->head = q; else si->tail->qnext = q; si->tail = q; /* advance the tail pointer */ q->qnext = si->head; /* make it circular */ } /* Remove the head queue from circular list. */ static inline void rr_remove_head(struct rr_si *si) { if (si->head == NULL) return; /* empty queue */ si->head->status = 0; if (si->head == si->tail) { si->head = si->tail = NULL; return; } si->head = si->head->qnext; si->tail->qnext = si->head; } /* Remove a queue from circular list. * XXX see if ti can be merge with remove_queue() */ static inline void remove_queue_q(struct rr_queue *q, struct rr_si *si) { struct rr_queue *prev; if (q->status != 1) return; if (q == si->head) { rr_remove_head(si); return; } for (prev = si->head; prev; prev = prev->qnext) { if (prev->qnext != q) continue; prev->qnext = q->qnext; if (q == si->tail) si->tail = prev; q->status = 0; break; } } static inline void next_pointer(struct rr_si *si) { if (si->head == NULL) return; /* empty queue */ si->head = si->head->qnext; si->tail = si->tail->qnext; } static int rr_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) { struct rr_si *si; struct rr_queue *rrq; if (m != q->mq.head) { if (dn_enqueue(q, m, 0)) /* packet was dropped */ return 1; if (m != q->mq.head) return 0; } /* If reach this point, queue q was idle */ si = (struct rr_si *)(_si + 1); rrq = (struct rr_queue *)q; if (rrq->status == 1) /* Queue is already in the queue list */ return 0; /* Insert the queue in the queue list */ rr_append(rrq, si); return 0; } static struct mbuf * rr_dequeue(struct dn_sch_inst *_si) { /* Access scheduler instance private data */ struct rr_si *si = (struct rr_si *)(_si + 1); struct rr_queue *rrq; uint64_t len; while ( (rrq = si->head) ) { struct mbuf *m = rrq->q.mq.head; if ( m == NULL) { /* empty queue, remove from list */ rr_remove_head(si); continue; } len = m->m_pkthdr.len; if (len > rrq->credit) { /* Packet too big */ rrq->credit += rrq->quantum; /* Try next queue */ next_pointer(si); } else { rrq->credit -= len; return dn_dequeue(&rrq->q); } } /* no packet to dequeue*/ return NULL; } static int rr_config(struct dn_schk *_schk) { struct rr_schk *schk = (struct rr_schk *)(_schk + 1); ND("called"); /* use reasonable quantums (64..2k bytes, default 1500) */ schk->min_q = 64; schk->max_q = 2048; schk->q_bytes = 1500; /* quantum */ return 0; } static int rr_new_sched(struct dn_sch_inst *_si) { struct rr_si *si = (struct rr_si *)(_si + 1); ND("called"); si->head = si->tail = NULL; return 0; } static int rr_free_sched(struct dn_sch_inst *_si) { (void)_si; ND("called"); /* Nothing to do? */ return 0; } static int rr_new_fsk(struct dn_fsk *fs) { struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1); /* par[0] is the weight, par[1] is the quantum step */ /* make sure the product fits an uint32_t */ ipdn_bound_var(&fs->fs.par[0], 1, 1, 65536, "RR weight"); ipdn_bound_var(&fs->fs.par[1], schk->q_bytes, schk->min_q, schk->max_q, "RR quantum"); return 0; } static int rr_new_queue(struct dn_queue *_q) { struct rr_queue *q = (struct rr_queue *)_q; uint64_t quantum; _q->ni.oid.subtype = DN_SCHED_RR; quantum = (uint64_t)_q->fs->fs.par[0] * _q->fs->fs.par[1]; if (quantum >= (1ULL<< 32)) { D("quantum too large, truncating to 4G - 1"); quantum = (1ULL<< 32) - 1; } q->quantum = quantum; ND("called, q->quantum %d", q->quantum); q->credit = q->quantum; q->status = 0; if (_q->mq.head != NULL) { /* Queue NOT empty, insert in the queue list */ rr_append(q, (struct rr_si *)(_q->_si + 1)); } return 0; } static int rr_free_queue(struct dn_queue *_q) { struct rr_queue *q = (struct rr_queue *)_q; ND("called"); if (q->status == 1) { struct rr_si *si = (struct rr_si *)(_q->_si + 1); remove_queue_q(q, si); } return 0; } /* * RR scheduler descriptor * contains the type of the scheduler, the name, the size of the * structures and function pointers. */ static struct dn_alg rr_desc = { _SI( .type = ) DN_SCHED_RR, _SI( .name = ) "RR", _SI( .flags = ) DN_MULTIQUEUE, _SI( .schk_datalen = ) sizeof(struct rr_schk), _SI( .si_datalen = ) sizeof(struct rr_si), _SI( .q_datalen = ) sizeof(struct rr_queue) - sizeof(struct dn_queue), _SI( .enqueue = ) rr_enqueue, _SI( .dequeue = ) rr_dequeue, _SI( .config = ) rr_config, _SI( .destroy = ) NULL, _SI( .new_sched = ) rr_new_sched, _SI( .free_sched = ) rr_free_sched, _SI( .new_fsk = ) rr_new_fsk, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) rr_new_queue, _SI( .free_queue = ) rr_free_queue, #ifdef NEW_AQM _SI( .getconfig = ) NULL, #endif }; DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc); Index: stable/11/sys/netpfil/ipfw/dn_sched_wf2q.c =================================================================== --- stable/11/sys/netpfil/ipfw/dn_sched_wf2q.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/dn_sched_wf2q.c (revision 325730) @@ -1,380 +1,383 @@ /* * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa * Copyright (c) 2000-2002 Luigi Rizzo, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * $FreeBSD$ */ #ifdef _KERNEL #include #include #include #include +#include #include #include +#include #include /* IFNAMSIZ */ #include #include /* ipfw_rule_ref */ #include /* flow_id */ #include +#include #include #include #ifdef NEW_AQM #include #endif #include #else #include #endif #ifndef MAX64 #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) #endif /* * timestamps are computed on 64 bit using fixed point arithmetic. * LMAX_BITS, WMAX_BITS are the max number of bits for the packet len * and sum of weights, respectively. FRAC_BITS is the number of * fractional bits. We want FRAC_BITS >> WMAX_BITS to avoid too large * errors when computing the inverse, FRAC_BITS < 32 so we can do 1/w * using an unsigned 32-bit division, and to avoid wraparounds we need * LMAX_BITS + WMAX_BITS + FRAC_BITS << 64 * As an example * FRAC_BITS = 26, LMAX_BITS=14, WMAX_BITS = 19 */ #ifndef FRAC_BITS #define FRAC_BITS 28 /* shift for fixed point arithmetic */ #define ONE_FP (1UL << FRAC_BITS) #endif /* * Private information for the scheduler instance: * sch_heap (key is Finish time) returns the next queue to serve * ne_heap (key is Start time) stores not-eligible queues * idle_heap (key=start/finish time) stores idle flows. It must * support extract-from-middle. * A flow is only in 1 of the three heaps. * XXX todo: use a more efficient data structure, e.g. a tree sorted * by F with min_subtree(S) in each node */ struct wf2qp_si { struct dn_heap sch_heap; /* top extract - key Finish time */ struct dn_heap ne_heap; /* top extract - key Start time */ struct dn_heap idle_heap; /* random extract - key Start=Finish time */ uint64_t V; /* virtual time */ uint32_t inv_wsum; /* inverse of sum of weights */ uint32_t wsum; /* sum of weights */ }; struct wf2qp_queue { struct dn_queue _q; uint64_t S, F; /* start time, finish time */ uint32_t inv_w; /* ONE_FP / weight */ int32_t heap_pos; /* position (index) of struct in heap */ }; /* * This file implements a WF2Q+ scheduler as it has been in dummynet * since 2000. * The scheduler supports per-flow queues and has O(log N) complexity. * * WF2Q+ needs to drain entries from the idle heap so that we * can keep the sum of weights up to date. We can do it whenever * we get a chance, or periodically, or following some other * strategy. The function idle_check() drains at most N elements * from the idle heap. */ static void idle_check(struct wf2qp_si *si, int n, int force) { struct dn_heap *h = &si->idle_heap; while (n-- > 0 && h->elements > 0 && (force || DN_KEY_LT(HEAP_TOP(h)->key, si->V))) { struct dn_queue *q = HEAP_TOP(h)->object; struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q; heap_extract(h, NULL); /* XXX to let the flowset delete the queue we should * mark it as 'unused' by the scheduler. */ alg_fq->S = alg_fq->F + 1; /* Mark timestamp as invalid. */ si->wsum -= q->fs->fs.par[0]; /* adjust sum of weights */ if (si->wsum > 0) si->inv_wsum = ONE_FP/si->wsum; } } static int wf2qp_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) { struct dn_fsk *fs = q->fs; struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1); struct wf2qp_queue *alg_fq; uint64_t len = m->m_pkthdr.len; if (m != q->mq.head) { if (dn_enqueue(q, m, 0)) /* packet was dropped */ return 1; if (m != q->mq.head) /* queue was already busy */ return 0; } /* If reach this point, queue q was idle */ alg_fq = (struct wf2qp_queue *)q; if (DN_KEY_LT(alg_fq->F, alg_fq->S)) { /* Fbrand new queue. */ alg_fq->S = si->V; /* init start time */ si->wsum += fs->fs.par[0]; /* add weight of new queue. */ si->inv_wsum = ONE_FP/si->wsum; } else { /* if it was idle then it was in the idle heap */ heap_extract(&si->idle_heap, q); alg_fq->S = MAX64(alg_fq->F, si->V); /* compute new S */ } alg_fq->F = alg_fq->S + len * alg_fq->inv_w; /* if nothing is backlogged, make sure this flow is eligible */ if (si->ne_heap.elements == 0 && si->sch_heap.elements == 0) si->V = MAX64(alg_fq->S, si->V); /* * Look at eligibility. A flow is not eligibile if S>V (when * this happens, it means that there is some other flow already * scheduled for the same pipe, so the sch_heap cannot be * empty). If the flow is not eligible we just store it in the * ne_heap. Otherwise, we store in the sch_heap. * Note that for all flows in sch_heap (SCH), S_i <= V, * and for all flows in ne_heap (NEH), S_i > V. * So when we need to compute max(V, min(S_i)) forall i in * SCH+NEH, we only need to look into NEH. */ if (DN_KEY_LT(si->V, alg_fq->S)) { /* S>V means flow Not eligible. */ if (si->sch_heap.elements == 0) D("++ ouch! not eligible but empty scheduler!"); heap_insert(&si->ne_heap, alg_fq->S, q); } else { heap_insert(&si->sch_heap, alg_fq->F, q); } return 0; } /* XXX invariant: sch > 0 || V >= min(S in neh) */ static struct mbuf * wf2qp_dequeue(struct dn_sch_inst *_si) { /* Access scheduler instance private data */ struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1); struct mbuf *m; struct dn_queue *q; struct dn_heap *sch = &si->sch_heap; struct dn_heap *neh = &si->ne_heap; struct wf2qp_queue *alg_fq; if (sch->elements == 0 && neh->elements == 0) { /* we have nothing to do. We could kill the idle heap * altogether and reset V */ idle_check(si, 0x7fffffff, 1); si->V = 0; si->wsum = 0; /* should be set already */ return NULL; /* quick return if nothing to do */ } idle_check(si, 1, 0); /* drain something from the idle heap */ /* make sure at least one element is eligible, bumping V * and moving entries that have become eligible. * We need to repeat the first part twice, before and * after extracting the candidate, or enqueue() will * find the data structure in a wrong state. */ m = NULL; for(;;) { /* * Compute V = max(V, min(S_i)). Remember that all elements * in sch have by definition S_i <= V so if sch is not empty, * V is surely the max and we must not update it. Conversely, * if sch is empty we only need to look at neh. * We don't need to move the queues, as it will be done at the * next enqueue */ if (sch->elements == 0 && neh->elements > 0) { si->V = MAX64(si->V, HEAP_TOP(neh)->key); } while (neh->elements > 0 && DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) { q = HEAP_TOP(neh)->object; alg_fq = (struct wf2qp_queue *)q; heap_extract(neh, NULL); heap_insert(sch, alg_fq->F, q); } if (m) /* pkt found in previous iteration */ break; /* ok we have at least one eligible pkt */ q = HEAP_TOP(sch)->object; alg_fq = (struct wf2qp_queue *)q; m = dn_dequeue(q); heap_extract(sch, NULL); /* Remove queue from heap. */ si->V += (uint64_t)(m->m_pkthdr.len) * si->inv_wsum; alg_fq->S = alg_fq->F; /* Update start time. */ if (q->mq.head == 0) { /* not backlogged any more. */ heap_insert(&si->idle_heap, alg_fq->F, q); } else { /* Still backlogged. */ /* Update F, store in neh or sch */ uint64_t len = q->mq.head->m_pkthdr.len; alg_fq->F += len * alg_fq->inv_w; if (DN_KEY_LEQ(alg_fq->S, si->V)) { heap_insert(sch, alg_fq->F, q); } else { heap_insert(neh, alg_fq->S, q); } } } return m; } static int wf2qp_new_sched(struct dn_sch_inst *_si) { struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1); int ofs = offsetof(struct wf2qp_queue, heap_pos); /* all heaps support extract from middle */ if (heap_init(&si->idle_heap, 16, ofs) || heap_init(&si->sch_heap, 16, ofs) || heap_init(&si->ne_heap, 16, ofs)) { heap_free(&si->ne_heap); heap_free(&si->sch_heap); heap_free(&si->idle_heap); return ENOMEM; } return 0; } static int wf2qp_free_sched(struct dn_sch_inst *_si) { struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1); heap_free(&si->sch_heap); heap_free(&si->ne_heap); heap_free(&si->idle_heap); return 0; } static int wf2qp_new_fsk(struct dn_fsk *fs) { ipdn_bound_var(&fs->fs.par[0], 1, 1, 100, "WF2Q+ weight"); return 0; } static int wf2qp_new_queue(struct dn_queue *_q) { struct wf2qp_queue *q = (struct wf2qp_queue *)_q; _q->ni.oid.subtype = DN_SCHED_WF2QP; q->F = 0; /* not strictly necessary */ q->S = q->F + 1; /* mark timestamp as invalid. */ q->inv_w = ONE_FP / _q->fs->fs.par[0]; if (_q->mq.head != NULL) { wf2qp_enqueue(_q->_si, _q, _q->mq.head); } return 0; } /* * Called when the infrastructure removes a queue (e.g. flowset * is reconfigured). Nothing to do if we did not 'own' the queue, * otherwise remove it from the right heap and adjust the sum * of weights. */ static int wf2qp_free_queue(struct dn_queue *q) { struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q; struct wf2qp_si *si = (struct wf2qp_si *)(q->_si + 1); if (alg_fq->S >= alg_fq->F + 1) return 0; /* nothing to do, not in any heap */ si->wsum -= q->fs->fs.par[0]; if (si->wsum > 0) si->inv_wsum = ONE_FP/si->wsum; /* extract from the heap. XXX TODO we may need to adjust V * to make sure the invariants hold. */ if (q->mq.head == NULL) { heap_extract(&si->idle_heap, q); } else if (DN_KEY_LT(si->V, alg_fq->S)) { heap_extract(&si->ne_heap, q); } else { heap_extract(&si->sch_heap, q); } return 0; } /* * WF2Q+ scheduler descriptor * contains the type of the scheduler, the name, the size of the * structures and function pointers. */ static struct dn_alg wf2qp_desc = { _SI( .type = ) DN_SCHED_WF2QP, _SI( .name = ) "WF2Q+", _SI( .flags = ) DN_MULTIQUEUE, /* we need extra space in the si and the queue */ _SI( .schk_datalen = ) 0, _SI( .si_datalen = ) sizeof(struct wf2qp_si), _SI( .q_datalen = ) sizeof(struct wf2qp_queue) - sizeof(struct dn_queue), _SI( .enqueue = ) wf2qp_enqueue, _SI( .dequeue = ) wf2qp_dequeue, _SI( .config = ) NULL, _SI( .destroy = ) NULL, _SI( .new_sched = ) wf2qp_new_sched, _SI( .free_sched = ) wf2qp_free_sched, _SI( .new_fsk = ) wf2qp_new_fsk, _SI( .free_fsk = ) NULL, _SI( .new_queue = ) wf2qp_new_queue, _SI( .free_queue = ) wf2qp_free_queue, #ifdef NEW_AQM _SI( .getconfig = ) NULL, #endif }; DECLARE_DNSCHED_MODULE(dn_wf2qp, &wf2qp_desc); Index: stable/11/sys/netpfil/ipfw/ip_dn_io.c =================================================================== --- stable/11/sys/netpfil/ipfw/ip_dn_io.c (revision 325729) +++ stable/11/sys/netpfil/ipfw/ip_dn_io.c (revision 325730) @@ -1,984 +1,968 @@ /*- * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * Dummynet portions related to packet handling. */ #include __FBSDID("$FreeBSD$"); #include "opt_inet6.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */ #include #include #include #include /* ip_len, ip_off */ #include /* ip_output(), IP_FORWARDING */ #include #include #include /* various ether_* routines */ #include /* for ip6_input, ip6_output prototypes */ #include #include #include #include #ifdef NEW_AQM #include #endif #include /* * We keep a private variable for the simulation time, but we could * probably use an existing one ("softticks" in sys/kern/kern_timeout.c) * instead of dn_cfg.curr_time */ struct dn_parms dn_cfg; //VNET_DEFINE(struct dn_parms, _base_dn_cfg); static long tick_last; /* Last tick duration (usec). */ static long tick_delta; /* Last vs standard tick diff (usec). */ static long tick_delta_sum; /* Accumulated tick difference (usec).*/ static long tick_adjustment; /* Tick adjustments done. */ static long tick_lost; /* Lost(coalesced) ticks number. */ /* Adjusted vs non-adjusted curr_time difference (ticks). */ static long tick_diff; static unsigned long io_pkt; static unsigned long io_pkt_fast; #ifdef NEW_AQM unsigned long io_pkt_drop; #else static unsigned long io_pkt_drop; #endif /* * We use a heap to store entities for which we have pending timer events. * The heap is checked at every tick and all entities with expired events * are extracted. */ MALLOC_DEFINE(M_DUMMYNET, "dummynet", "dummynet heap"); extern void (*bridge_dn_p)(struct mbuf *, struct ifnet *); #ifdef SYSCTL_NODE /* * Because of the way the SYSBEGIN/SYSEND macros work on other * platforms, there should not be functions between them. * So keep the handlers outside the block. */ static int sysctl_hash_size(SYSCTL_HANDLER_ARGS) { int error, value; value = dn_cfg.hash_size; error = sysctl_handle_int(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (value < 16 || value > 65536) return (EINVAL); dn_cfg.hash_size = value; return (0); } static int sysctl_limits(SYSCTL_HANDLER_ARGS) { int error; long value; if (arg2 != 0) value = dn_cfg.slot_limit; else value = dn_cfg.byte_limit; error = sysctl_handle_long(oidp, &value, 0, req); if (error != 0 || req->newptr == NULL) return (error); if (arg2 != 0) { if (value < 1) return (EINVAL); dn_cfg.slot_limit = value; } else { if (value < 1500) return (EINVAL); dn_cfg.byte_limit = value; } return (0); } SYSBEGIN(f4) SYSCTL_DECL(_net_inet); SYSCTL_DECL(_net_inet_ip); #ifdef NEW_AQM SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet, CTLFLAG_RW, 0, "Dummynet"); #else static SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet, CTLFLAG_RW, 0, "Dummynet"); #endif /* wrapper to pass dn_cfg fields to SYSCTL_* */ //#define DC(x) (&(VNET_NAME(_base_dn_cfg).x)) #define DC(x) (&(dn_cfg.x)) /* parameters */ SYSCTL_PROC(_net_inet_ip_dummynet, OID_AUTO, hash_size, CTLTYPE_INT | CTLFLAG_RW, 0, 0, sysctl_hash_size, "I", "Default hash table size"); SYSCTL_PROC(_net_inet_ip_dummynet, OID_AUTO, pipe_slot_limit, CTLTYPE_LONG | CTLFLAG_RW, 0, 1, sysctl_limits, "L", "Upper limit in slots for pipe queue."); SYSCTL_PROC(_net_inet_ip_dummynet, OID_AUTO, pipe_byte_limit, CTLTYPE_LONG | CTLFLAG_RW, 0, 0, sysctl_limits, "L", "Upper limit in bytes for pipe queue."); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, io_fast, CTLFLAG_RW, DC(io_fast), 0, "Enable fast dummynet io."); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, debug, CTLFLAG_RW, DC(debug), 0, "Dummynet debug level"); /* RED parameters */ SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_lookup_depth, CTLFLAG_RD, DC(red_lookup_depth), 0, "Depth of RED lookup table"); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_avg_pkt_size, CTLFLAG_RD, DC(red_avg_pkt_size), 0, "RED Medium packet size"); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_max_pkt_size, CTLFLAG_RD, DC(red_max_pkt_size), 0, "RED Max packet size"); /* time adjustment */ SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_delta, CTLFLAG_RD, &tick_delta, 0, "Last vs standard tick difference (usec)."); SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_delta_sum, CTLFLAG_RD, &tick_delta_sum, 0, "Accumulated tick difference (usec)."); SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_adjustment, CTLFLAG_RD, &tick_adjustment, 0, "Tick adjustments done."); SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_diff, CTLFLAG_RD, &tick_diff, 0, "Adjusted vs non-adjusted curr_time difference (ticks)."); SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_lost, CTLFLAG_RD, &tick_lost, 0, "Number of ticks coalesced by dummynet taskqueue."); /* Drain parameters */ SYSCTL_UINT(_net_inet_ip_dummynet, OID_AUTO, expire, CTLFLAG_RW, DC(expire), 0, "Expire empty queues/pipes"); SYSCTL_UINT(_net_inet_ip_dummynet, OID_AUTO, expire_cycle, CTLFLAG_RD, DC(expire_cycle), 0, "Expire cycle for queues/pipes"); /* statistics */ SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, schk_count, CTLFLAG_RD, DC(schk_count), 0, "Number of schedulers"); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, si_count, CTLFLAG_RD, DC(si_count), 0, "Number of scheduler instances"); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, fsk_count, CTLFLAG_RD, DC(fsk_count), 0, "Number of flowsets"); SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, queue_count, CTLFLAG_RD, DC(queue_count), 0, "Number of queues"); SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt, CTLFLAG_RD, &io_pkt, 0, "Number of packets passed to dummynet."); SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt_fast, CTLFLAG_RD, &io_pkt_fast, 0, "Number of packets bypassed dummynet scheduler."); SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt_drop, CTLFLAG_RD, &io_pkt_drop, 0, "Number of packets dropped by dummynet."); #undef DC SYSEND #endif static void dummynet_send(struct mbuf *); /* - * Packets processed by dummynet have an mbuf tag associated with - * them that carries their dummynet state. - * Outside dummynet, only the 'rule' field is relevant, and it must - * be at the beginning of the structure. - */ -struct dn_pkt_tag { - struct ipfw_rule_ref rule; /* matching rule */ - - /* second part, dummynet specific */ - int dn_dir; /* action when packet comes out.*/ - /* see ip_fw_private.h */ - uint64_t output_time; /* when the pkt is due for delivery*/ - struct ifnet *ifp; /* interface, for ip_output */ - struct _ip6dn_args ip6opt; /* XXX ipv6 options */ -}; - -/* * Return the mbuf tag holding the dummynet state (it should * be the first one on the list). */ -static struct dn_pkt_tag * +struct dn_pkt_tag * dn_tag_get(struct mbuf *m) { struct m_tag *mtag = m_tag_first(m); #ifdef NEW_AQM /* XXX: to skip ts m_tag. For Debugging only*/ if (mtag != NULL && mtag->m_tag_id == DN_AQM_MTAG_TS) { m_tag_delete(m,mtag); mtag = m_tag_first(m); D("skip TS tag"); } #endif KASSERT(mtag != NULL && mtag->m_tag_cookie == MTAG_ABI_COMPAT && mtag->m_tag_id == PACKET_TAG_DUMMYNET, ("packet on dummynet queue w/o dummynet tag!")); return (struct dn_pkt_tag *)(mtag+1); } #ifndef NEW_AQM static inline void mq_append(struct mq *q, struct mbuf *m) { #ifdef USERSPACE // buffers from netmap need to be copied // XXX note that the routine is not expected to fail ND("append %p to %p", m, q); if (m->m_flags & M_STACK) { struct mbuf *m_new; void *p; int l, ofs; ofs = m->m_data - m->__m_extbuf; // XXX allocate MGETHDR(m_new, M_NOWAIT, MT_DATA); ND("*** WARNING, volatile buf %p ext %p %d dofs %d m_new %p", m, m->__m_extbuf, m->__m_extlen, ofs, m_new); p = m_new->__m_extbuf; /* new pointer */ l = m_new->__m_extlen; /* new len */ if (l <= m->__m_extlen) { panic("extlen too large"); } *m_new = *m; // copy m_new->m_flags &= ~M_STACK; m_new->__m_extbuf = p; // point to new buffer _pkt_copy(m->__m_extbuf, p, m->__m_extlen); m_new->m_data = p + ofs; m = m_new; } #endif /* USERSPACE */ if (q->head == NULL) q->head = m; else q->tail->m_nextpkt = m; q->count++; q->tail = m; m->m_nextpkt = NULL; } #endif /* * Dispose a list of packet. Use a functions so if we need to do * more work, this is a central point to do it. */ void dn_free_pkts(struct mbuf *mnext) { struct mbuf *m; while ((m = mnext) != NULL) { mnext = m->m_nextpkt; FREE_PKT(m); } } static int red_drops (struct dn_queue *q, int len) { /* * RED algorithm * * RED calculates the average queue size (avg) using a low-pass filter * with an exponential weighted (w_q) moving average: * avg <- (1-w_q) * avg + w_q * q_size * where q_size is the queue length (measured in bytes or * packets). * * If q_size == 0, we compute the idle time for the link, and set * avg = (1 - w_q)^(idle/s) * where s is the time needed for transmitting a medium-sized packet. * * Now, if avg < min_th the packet is enqueued. * If avg > max_th the packet is dropped. Otherwise, the packet is * dropped with probability P function of avg. */ struct dn_fsk *fs = q->fs; int64_t p_b = 0; /* Queue in bytes or packets? */ uint32_t q_size = (fs->fs.flags & DN_QSIZE_BYTES) ? q->ni.len_bytes : q->ni.length; /* Average queue size estimation. */ if (q_size != 0) { /* Queue is not empty, avg <- avg + (q_size - avg) * w_q */ int diff = SCALE(q_size) - q->avg; int64_t v = SCALE_MUL((int64_t)diff, (int64_t)fs->w_q); q->avg += (int)v; } else { /* * Queue is empty, find for how long the queue has been * empty and use a lookup table for computing * (1 - * w_q)^(idle_time/s) where s is the time to send a * (small) packet. * XXX check wraps... */ if (q->avg) { u_int t = div64((dn_cfg.curr_time - q->q_time), fs->lookup_step); q->avg = (t < fs->lookup_depth) ? SCALE_MUL(q->avg, fs->w_q_lookup[t]) : 0; } } /* Should i drop? */ if (q->avg < fs->min_th) { q->count = -1; return (0); /* accept packet */ } if (q->avg >= fs->max_th) { /* average queue >= max threshold */ if (fs->fs.flags & DN_IS_ECN) return (1); if (fs->fs.flags & DN_IS_GENTLE_RED) { /* * According to Gentle-RED, if avg is greater than * max_th the packet is dropped with a probability * p_b = c_3 * avg - c_4 * where c_3 = (1 - max_p) / max_th * c_4 = 1 - 2 * max_p */ p_b = SCALE_MUL((int64_t)fs->c_3, (int64_t)q->avg) - fs->c_4; } else { q->count = -1; return (1); } } else if (q->avg > fs->min_th) { if (fs->fs.flags & DN_IS_ECN) return (1); /* * We compute p_b using the linear dropping function * p_b = c_1 * avg - c_2 * where c_1 = max_p / (max_th - min_th) * c_2 = max_p * min_th / (max_th - min_th) */ p_b = SCALE_MUL((int64_t)fs->c_1, (int64_t)q->avg) - fs->c_2; } if (fs->fs.flags & DN_QSIZE_BYTES) p_b = div64((p_b * len) , fs->max_pkt_size); if (++q->count == 0) q->random = random() & 0xffff; else { /* * q->count counts packets arrived since last drop, so a greater * value of q->count means a greater packet drop probability. */ if (SCALE_MUL(p_b, SCALE((int64_t)q->count)) > q->random) { q->count = 0; /* After a drop we calculate a new random value. */ q->random = random() & 0xffff; return (1); /* drop */ } } /* End of RED algorithm. */ return (0); /* accept */ } /* * ECN/ECT Processing (partially adopted from altq) */ #ifndef NEW_AQM static #endif int ecn_mark(struct mbuf* m) { struct ip *ip; - ip = mtod(m, struct ip *); + ip = (struct ip *)mtodo(m, dn_tag_get(m)->iphdr_off); switch (ip->ip_v) { case IPVERSION: { uint16_t old; if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT) return (0); /* not-ECT */ if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE) return (1); /* already marked */ /* * ecn-capable but not marked, * mark CE and update checksum */ old = *(uint16_t *)ip; ip->ip_tos |= IPTOS_ECN_CE; ip->ip_sum = cksum_adjust(ip->ip_sum, old, *(uint16_t *)ip); return (1); } #ifdef INET6 case (IPV6_VERSION >> 4): { - struct ip6_hdr *ip6 = mtod(m, struct ip6_hdr *); + struct ip6_hdr *ip6 = (struct ip6_hdr *)ip; u_int32_t flowlabel; flowlabel = ntohl(ip6->ip6_flow); if ((flowlabel >> 28) != 6) return (0); /* version mismatch! */ if ((flowlabel & (IPTOS_ECN_MASK << 20)) == (IPTOS_ECN_NOTECT << 20)) return (0); /* not-ECT */ if ((flowlabel & (IPTOS_ECN_MASK << 20)) == (IPTOS_ECN_CE << 20)) return (1); /* already marked */ /* * ecn-capable but not marked, mark CE */ flowlabel |= (IPTOS_ECN_CE << 20); ip6->ip6_flow = htonl(flowlabel); return (1); } #endif } return (0); } /* * Enqueue a packet in q, subject to space and queue management policy * (whose parameters are in q->fs). * Update stats for the queue and the scheduler. * Return 0 on success, 1 on drop. The packet is consumed anyways. */ int dn_enqueue(struct dn_queue *q, struct mbuf* m, int drop) { struct dn_fs *f; struct dn_flow *ni; /* stats for scheduler instance */ uint64_t len; if (q->fs == NULL || q->_si == NULL) { printf("%s fs %p si %p, dropping\n", __FUNCTION__, q->fs, q->_si); FREE_PKT(m); return 1; } f = &(q->fs->fs); ni = &q->_si->ni; len = m->m_pkthdr.len; /* Update statistics, then check reasons to drop pkt. */ q->ni.tot_bytes += len; q->ni.tot_pkts++; ni->tot_bytes += len; ni->tot_pkts++; if (drop) goto drop; if (f->plr && random() < f->plr) goto drop; #ifdef NEW_AQM /* Call AQM enqueue function */ if (q->fs->aqmfp) return q->fs->aqmfp->enqueue(q ,m); #endif if (f->flags & DN_IS_RED && red_drops(q, m->m_pkthdr.len)) { if (!(f->flags & DN_IS_ECN) || !ecn_mark(m)) goto drop; } if (f->flags & DN_QSIZE_BYTES) { if (q->ni.len_bytes > f->qsize) goto drop; } else if (q->ni.length >= f->qsize) { goto drop; } mq_append(&q->mq, m); q->ni.length++; q->ni.len_bytes += len; ni->length++; ni->len_bytes += len; return (0); drop: io_pkt_drop++; q->ni.drops++; ni->drops++; FREE_PKT(m); return (1); } /* * Fetch packets from the delay line which are due now. If there are * leftover packets, reinsert the delay line in the heap. * Runs under scheduler lock. */ static void transmit_event(struct mq *q, struct delay_line *dline, uint64_t now) { struct mbuf *m; struct dn_pkt_tag *pkt = NULL; dline->oid.subtype = 0; /* not in heap */ while ((m = dline->mq.head) != NULL) { pkt = dn_tag_get(m); if (!DN_KEY_LEQ(pkt->output_time, now)) break; dline->mq.head = m->m_nextpkt; dline->mq.count--; mq_append(q, m); } if (m != NULL) { dline->oid.subtype = 1; /* in heap */ heap_insert(&dn_cfg.evheap, pkt->output_time, dline); } } /* * Convert the additional MAC overheads/delays into an equivalent * number of bits for the given data rate. The samples are * in milliseconds so we need to divide by 1000. */ static uint64_t extra_bits(struct mbuf *m, struct dn_schk *s) { int index; uint64_t bits; struct dn_profile *pf = s->profile; if (!pf || pf->samples_no == 0) return 0; index = random() % pf->samples_no; bits = div64((uint64_t)pf->samples[index] * s->link.bandwidth, 1000); if (index >= pf->loss_level) { struct dn_pkt_tag *dt = dn_tag_get(m); if (dt) dt->dn_dir = DIR_DROP; } return bits; } /* * Send traffic from a scheduler instance due by 'now'. * Return a pointer to the head of the queue. */ static struct mbuf * serve_sched(struct mq *q, struct dn_sch_inst *si, uint64_t now) { struct mq def_q; struct dn_schk *s = si->sched; struct mbuf *m = NULL; int delay_line_idle = (si->dline.mq.head == NULL); int done, bw; if (q == NULL) { q = &def_q; q->head = NULL; } bw = s->link.bandwidth; si->kflags &= ~DN_ACTIVE; if (bw > 0) si->credit += (now - si->sched_time) * bw; else si->credit = 0; si->sched_time = now; done = 0; while (si->credit >= 0 && (m = s->fp->dequeue(si)) != NULL) { uint64_t len_scaled; done++; len_scaled = (bw == 0) ? 0 : hz * (m->m_pkthdr.len * 8 + extra_bits(m, s)); si->credit -= len_scaled; /* Move packet in the delay line */ dn_tag_get(m)->output_time = dn_cfg.curr_time + s->link.delay ; mq_append(&si->dline.mq, m); } /* * If credit >= 0 the instance is idle, mark time. * Otherwise put back in the heap, and adjust the output * time of the last inserted packet, m, which was too early. */ if (si->credit >= 0) { si->idle_time = now; } else { uint64_t t; KASSERT (bw > 0, ("bw=0 and credit<0 ?")); t = div64(bw - 1 - si->credit, bw); if (m) dn_tag_get(m)->output_time += t; si->kflags |= DN_ACTIVE; heap_insert(&dn_cfg.evheap, now + t, si); } if (delay_line_idle && done) transmit_event(q, &si->dline, now); return q->head; } /* * The timer handler for dummynet. Time is computed in ticks, but * but the code is tolerant to the actual rate at which this is called. * Once complete, the function reschedules itself for the next tick. */ void dummynet_task(void *context, int pending) { struct timeval t; struct mq q = { NULL, NULL }; /* queue to accumulate results */ CURVNET_SET((struct vnet *)context); DN_BH_WLOCK(); /* Update number of lost(coalesced) ticks. */ tick_lost += pending - 1; getmicrouptime(&t); /* Last tick duration (usec). */ tick_last = (t.tv_sec - dn_cfg.prev_t.tv_sec) * 1000000 + (t.tv_usec - dn_cfg.prev_t.tv_usec); /* Last tick vs standard tick difference (usec). */ tick_delta = (tick_last * hz - 1000000) / hz; /* Accumulated tick difference (usec). */ tick_delta_sum += tick_delta; dn_cfg.prev_t = t; /* * Adjust curr_time if the accumulated tick difference is * greater than the 'standard' tick. Since curr_time should * be monotonically increasing, we do positive adjustments * as required, and throttle curr_time in case of negative * adjustment. */ dn_cfg.curr_time++; if (tick_delta_sum - tick >= 0) { int diff = tick_delta_sum / tick; dn_cfg.curr_time += diff; tick_diff += diff; tick_delta_sum %= tick; tick_adjustment++; } else if (tick_delta_sum + tick <= 0) { dn_cfg.curr_time--; tick_diff--; tick_delta_sum += tick; tick_adjustment++; } /* serve pending events, accumulate in q */ for (;;) { struct dn_id *p; /* generic parameter to handler */ if (dn_cfg.evheap.elements == 0 || DN_KEY_LT(dn_cfg.curr_time, HEAP_TOP(&dn_cfg.evheap)->key)) break; p = HEAP_TOP(&dn_cfg.evheap)->object; heap_extract(&dn_cfg.evheap, NULL); if (p->type == DN_SCH_I) { serve_sched(&q, (struct dn_sch_inst *)p, dn_cfg.curr_time); } else { /* extracted a delay line */ transmit_event(&q, (struct delay_line *)p, dn_cfg.curr_time); } } if (dn_cfg.expire && ++dn_cfg.expire_cycle >= dn_cfg.expire) { dn_cfg.expire_cycle = 0; dn_drain_scheduler(); dn_drain_queue(); } dn_reschedule(); DN_BH_WUNLOCK(); if (q.head != NULL) dummynet_send(q.head); CURVNET_RESTORE(); } /* * forward a chain of packets to the proper destination. * This runs outside the dummynet lock. */ static void dummynet_send(struct mbuf *m) { struct mbuf *n; for (; m != NULL; m = n) { struct ifnet *ifp = NULL; /* gcc 3.4.6 complains */ struct m_tag *tag; int dst; n = m->m_nextpkt; m->m_nextpkt = NULL; tag = m_tag_first(m); if (tag == NULL) { /* should not happen */ dst = DIR_DROP; } else { struct dn_pkt_tag *pkt = dn_tag_get(m); /* extract the dummynet info, rename the tag * to carry reinject info. */ if (pkt->dn_dir == (DIR_OUT | PROTO_LAYER2) && pkt->ifp == NULL) { dst = DIR_DROP; } else { dst = pkt->dn_dir; ifp = pkt->ifp; tag->m_tag_cookie = MTAG_IPFW_RULE; tag->m_tag_id = 0; } } switch (dst) { case DIR_OUT: ip_output(m, NULL, NULL, IP_FORWARDING, NULL, NULL); break ; case DIR_IN : netisr_dispatch(NETISR_IP, m); break; #ifdef INET6 case DIR_IN | PROTO_IPV6: netisr_dispatch(NETISR_IPV6, m); break; case DIR_OUT | PROTO_IPV6: ip6_output(m, NULL, NULL, IPV6_FORWARDING, NULL, NULL, NULL); break; #endif case DIR_FWD | PROTO_IFB: /* DN_TO_IFB_FWD: */ if (bridge_dn_p != NULL) ((*bridge_dn_p)(m, ifp)); else printf("dummynet: if_bridge not loaded\n"); break; case DIR_IN | PROTO_LAYER2: /* DN_TO_ETH_DEMUX: */ /* * The Ethernet code assumes the Ethernet header is * contiguous in the first mbuf header. * Insure this is true. */ if (m->m_len < ETHER_HDR_LEN && (m = m_pullup(m, ETHER_HDR_LEN)) == NULL) { printf("dummynet/ether: pullup failed, " "dropping packet\n"); break; } ether_demux(m->m_pkthdr.rcvif, m); break; case DIR_OUT | PROTO_LAYER2: /* N_TO_ETH_OUT: */ ether_output_frame(ifp, m); break; case DIR_DROP: /* drop the packet after some time */ FREE_PKT(m); break; default: printf("dummynet: bad switch %d!\n", dst); FREE_PKT(m); break; } } } static inline int tag_mbuf(struct mbuf *m, int dir, struct ip_fw_args *fwa) { struct dn_pkt_tag *dt; struct m_tag *mtag; mtag = m_tag_get(PACKET_TAG_DUMMYNET, sizeof(*dt), M_NOWAIT | M_ZERO); if (mtag == NULL) return 1; /* Cannot allocate packet header. */ m_tag_prepend(m, mtag); /* Attach to mbuf chain. */ dt = (struct dn_pkt_tag *)(mtag + 1); dt->rule = fwa->rule; dt->rule.info &= IPFW_ONEPASS; /* only keep this info */ dt->dn_dir = dir; dt->ifp = fwa->oif; /* dt->output tame is updated as we move through */ dt->output_time = dn_cfg.curr_time; + dt->iphdr_off = (dir & PROTO_LAYER2) ? ETHER_HDR_LEN : 0; return 0; } /* * dummynet hook for packets. * We use the argument to locate the flowset fs and the sched_set sch * associated to it. The we apply flow_mask and sched_mask to * determine the queue and scheduler instances. * * dir where shall we send the packet after dummynet. * *m0 the mbuf with the packet * ifp the 'ifp' parameter from the caller. * NULL in ip_input, destination interface in ip_output, */ int dummynet_io(struct mbuf **m0, int dir, struct ip_fw_args *fwa) { struct mbuf *m = *m0; struct dn_fsk *fs = NULL; struct dn_sch_inst *si; struct dn_queue *q = NULL; /* default */ int fs_id = (fwa->rule.info & IPFW_INFO_MASK) + ((fwa->rule.info & IPFW_IS_PIPE) ? 2*DN_MAX_ID : 0); DN_BH_WLOCK(); io_pkt++; /* we could actually tag outside the lock, but who cares... */ if (tag_mbuf(m, dir, fwa)) goto dropit; if (dn_cfg.busy) { /* if the upper half is busy doing something expensive, * lets queue the packet and move forward */ mq_append(&dn_cfg.pending, m); m = *m0 = NULL; /* consumed */ goto done; /* already active, nothing to do */ } /* XXX locate_flowset could be optimised with a direct ref. */ fs = dn_ht_find(dn_cfg.fshash, fs_id, 0, NULL); if (fs == NULL) goto dropit; /* This queue/pipe does not exist! */ if (fs->sched == NULL) /* should not happen */ goto dropit; /* find scheduler instance, possibly applying sched_mask */ si = ipdn_si_find(fs->sched, &(fwa->f_id)); if (si == NULL) goto dropit; /* * If the scheduler supports multiple queues, find the right one * (otherwise it will be ignored by enqueue). */ if (fs->sched->fp->flags & DN_MULTIQUEUE) { q = ipdn_q_find(fs, si, &(fwa->f_id)); if (q == NULL) goto dropit; } if (fs->sched->fp->enqueue(si, q, m)) { /* packet was dropped by enqueue() */ m = *m0 = NULL; /* dn_enqueue already increases io_pkt_drop */ io_pkt_drop--; goto dropit; } if (si->kflags & DN_ACTIVE) { m = *m0 = NULL; /* consumed */ goto done; /* already active, nothing to do */ } /* compute the initial allowance */ if (si->idle_time < dn_cfg.curr_time) { /* Do this only on the first packet on an idle pipe */ struct dn_link *p = &fs->sched->link; si->sched_time = dn_cfg.curr_time; si->credit = dn_cfg.io_fast ? p->bandwidth : 0; if (p->burst) { uint64_t burst = (dn_cfg.curr_time - si->idle_time) * p->bandwidth; if (burst > p->burst) burst = p->burst; si->credit += burst; } } /* pass through scheduler and delay line */ m = serve_sched(NULL, si, dn_cfg.curr_time); /* optimization -- pass it back to ipfw for immediate send */ /* XXX Don't call dummynet_send() if scheduler return the packet * just enqueued. This avoid a lock order reversal. * */ if (/*dn_cfg.io_fast &&*/ m == *m0 && (dir & PROTO_LAYER2) == 0 ) { /* fast io, rename the tag * to carry reinject info. */ struct m_tag *tag = m_tag_first(m); tag->m_tag_cookie = MTAG_IPFW_RULE; tag->m_tag_id = 0; io_pkt_fast++; if (m->m_nextpkt != NULL) { printf("dummynet: fast io: pkt chain detected!\n"); m->m_nextpkt = NULL; } m = NULL; } else { *m0 = NULL; } done: DN_BH_WUNLOCK(); if (m) dummynet_send(m); return 0; dropit: io_pkt_drop++; DN_BH_WUNLOCK(); if (m) FREE_PKT(m); *m0 = NULL; return (fs && (fs->fs.flags & DN_NOERROR)) ? 0 : ENOBUFS; } Index: stable/11/sys/netpfil/ipfw/ip_dn_private.h =================================================================== --- stable/11/sys/netpfil/ipfw/ip_dn_private.h (revision 325729) +++ stable/11/sys/netpfil/ipfw/ip_dn_private.h (revision 325730) @@ -1,463 +1,482 @@ /*- * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ /* * internal dummynet APIs. * * $FreeBSD$ */ #ifndef _IP_DN_PRIVATE_H #define _IP_DN_PRIVATE_H /* debugging support * use ND() to remove debugging, D() to print a line, * DX(level, ...) to print above a certain level * If you redefine D() you are expected to redefine all. */ #ifndef D #define ND(fmt, ...) do {} while (0) #define D1(fmt, ...) do {} while (0) #define D(fmt, ...) printf("%-10s " fmt "\n", \ __FUNCTION__, ## __VA_ARGS__) #define DX(lev, fmt, ...) do { \ if (dn_cfg.debug > lev) D(fmt, ## __VA_ARGS__); } while (0) #endif MALLOC_DECLARE(M_DUMMYNET); #ifndef __linux__ #define div64(a, b) ((int64_t)(a) / (int64_t)(b)) #endif #define DN_LOCK_INIT() do { \ mtx_init(&dn_cfg.uh_mtx, "dn_uh", NULL, MTX_DEF); \ mtx_init(&dn_cfg.bh_mtx, "dn_bh", NULL, MTX_DEF); \ } while (0) #define DN_LOCK_DESTROY() do { \ mtx_destroy(&dn_cfg.uh_mtx); \ mtx_destroy(&dn_cfg.bh_mtx); \ } while (0) #if 0 /* not used yet */ #define DN_UH_RLOCK() mtx_lock(&dn_cfg.uh_mtx) #define DN_UH_RUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) #define DN_UH_WLOCK() mtx_lock(&dn_cfg.uh_mtx) #define DN_UH_WUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) #define DN_UH_LOCK_ASSERT() mtx_assert(&dn_cfg.uh_mtx, MA_OWNED) #endif #define DN_BH_RLOCK() mtx_lock(&dn_cfg.uh_mtx) #define DN_BH_RUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) #define DN_BH_WLOCK() mtx_lock(&dn_cfg.uh_mtx) #define DN_BH_WUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) #define DN_BH_LOCK_ASSERT() mtx_assert(&dn_cfg.uh_mtx, MA_OWNED) SLIST_HEAD(dn_schk_head, dn_schk); SLIST_HEAD(dn_sch_inst_head, dn_sch_inst); SLIST_HEAD(dn_fsk_head, dn_fsk); SLIST_HEAD(dn_queue_head, dn_queue); SLIST_HEAD(dn_alg_head, dn_alg); #ifdef NEW_AQM SLIST_HEAD(dn_aqm_head, dn_aqm); /* for new AQMs */ #endif struct mq { /* a basic queue of packets*/ struct mbuf *head, *tail; int count; }; static inline void set_oid(struct dn_id *o, int type, int len) { o->type = type; o->len = len; o->subtype = 0; } /* * configuration and global data for a dummynet instance * * When a configuration is modified from userland, 'id' is incremented * so we can use the value to check for stale pointers. */ struct dn_parms { uint32_t id; /* configuration version */ /* defaults (sysctl-accessible) */ int red_lookup_depth; int red_avg_pkt_size; int red_max_pkt_size; int hash_size; int max_hash_size; long byte_limit; /* max queue sizes */ long slot_limit; int io_fast; int debug; /* timekeeping */ struct timeval prev_t; /* last time dummynet_tick ran */ struct dn_heap evheap; /* scheduled events */ /* counters of objects -- used for reporting space */ int schk_count; int si_count; int fsk_count; int queue_count; /* ticks and other stuff */ uint64_t curr_time; /* flowsets and schedulers are in hash tables, with 'hash_size' * buckets. fshash is looked up at every packet arrival * so better be generous if we expect many entries. */ struct dn_ht *fshash; struct dn_ht *schedhash; /* list of flowsets without a scheduler -- use sch_chain */ struct dn_fsk_head fsu; /* list of unlinked flowsets */ struct dn_alg_head schedlist; /* list of algorithms */ #ifdef NEW_AQM struct dn_aqm_head aqmlist; /* list of AQMs */ #endif /* Store the fs/sch to scan when draining. The value is the * bucket number of the hash table. Expire can be disabled * with net.inet.ip.dummynet.expire=0, or it happens every * expire ticks. **/ int drain_fs; int drain_sch; uint32_t expire; uint32_t expire_cycle; /* tick count */ int init_done; /* if the upper half is busy doing something long, * can set the busy flag and we will enqueue packets in * a queue for later processing. */ int busy; struct mq pending; #ifdef _KERNEL /* * This file is normally used in the kernel, unless we do * some userland tests, in which case we do not need a mtx. * uh_mtx arbitrates between system calls and also * protects fshash, schedhash and fsunlinked. * These structures are readonly for the lower half. * bh_mtx protects all other structures which may be * modified upon packet arrivals */ #if defined( __linux__ ) || defined( _WIN32 ) spinlock_t uh_mtx; spinlock_t bh_mtx; #else struct mtx uh_mtx; struct mtx bh_mtx; #endif #endif /* _KERNEL */ }; /* * Delay line, contains all packets on output from a link. * Every scheduler instance has one. */ struct delay_line { struct dn_id oid; struct dn_sch_inst *si; struct mq mq; }; /* * The kernel side of a flowset. It is linked in a hash table * of flowsets, and in a list of children of their parent scheduler. * qht is either the queue or (if HAVE_MASK) a hash table queues. * Note that the mask to use is the (flow_mask|sched_mask), which * changes as we attach/detach schedulers. So we store it here. * * XXX If we want to add scheduler-specific parameters, we need to * put them in external storage because the scheduler may not be * available when the fsk is created. */ struct dn_fsk { /* kernel side of a flowset */ struct dn_fs fs; SLIST_ENTRY(dn_fsk) fsk_next; /* hash chain for fshash */ struct ipfw_flow_id fsk_mask; /* qht is a hash table of queues, or just a single queue * a bit in fs.flags tells us which one */ struct dn_ht *qht; struct dn_schk *sched; /* Sched we are linked to */ SLIST_ENTRY(dn_fsk) sch_chain; /* list of fsk attached to sched */ /* bucket index used by drain routine to drain queues for this * flowset */ int drain_bucket; /* Parameter realted to RED / GRED */ /* original values are in dn_fs*/ int w_q ; /* queue weight (scaled) */ int max_th ; /* maximum threshold for queue (scaled) */ int min_th ; /* minimum threshold for queue (scaled) */ int max_p ; /* maximum value for p_b (scaled) */ u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ u_int lookup_depth ; /* depth of lookup table */ int lookup_step ; /* granularity inside the lookup table */ int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ int avg_pkt_size ; /* medium packet size */ int max_pkt_size ; /* max packet size */ #ifdef NEW_AQM struct dn_aqm *aqmfp; /* Pointer to AQM functions */ void *aqmcfg; /* configuration parameters for AQM */ #endif }; /* * A queue is created as a child of a flowset unless it belongs to * a !MULTIQUEUE scheduler. It is normally in a hash table in the * flowset. fs always points to the parent flowset. * si normally points to the sch_inst, unless the flowset has been * detached from the scheduler -- in this case si == NULL and we * should not enqueue. */ struct dn_queue { struct dn_flow ni; /* oid, flow_id, stats */ struct mq mq; /* packets queue */ struct dn_sch_inst *_si; /* owner scheduler instance */ SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */ struct dn_fsk *fs; /* parent flowset. */ /* RED parameters */ int avg; /* average queue length est. (scaled) */ int count; /* arrivals since last RED drop */ int random; /* random value (scaled) */ uint64_t q_time; /* start of queue idle time */ #ifdef NEW_AQM void *aqm_status; /* per-queue status variables*/ #endif }; /* * The kernel side of a scheduler. Contains the userland config, * a link, pointer to extra config arguments from command line, * kernel flags, and a pointer to the scheduler methods. * It is stored in a hash table, and holds a list of all * flowsets and scheduler instances. * XXX sch must be at the beginning, see schk_hash(). */ struct dn_schk { struct dn_sch sch; struct dn_alg *fp; /* Pointer to scheduler functions */ struct dn_link link; /* The link, embedded */ struct dn_profile *profile; /* delay profile, if any */ struct dn_id *cfg; /* extra config arguments */ SLIST_ENTRY(dn_schk) schk_next; /* hash chain for schedhash */ struct dn_fsk_head fsk_list; /* all fsk linked to me */ struct dn_fsk *fs; /* Flowset for !MULTIQUEUE */ /* bucket index used by the drain routine to drain the scheduler * instance for this flowset. */ int drain_bucket; /* Hash table of all instances (through sch.sched_mask) * or single instance if no mask. Always valid. */ struct dn_ht *siht; }; /* * Scheduler instance. * Contains variables and all queues relative to a this instance. * This struct is created a runtime. */ struct dn_sch_inst { struct dn_flow ni; /* oid, flowid and stats */ SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */ struct delay_line dline; struct dn_schk *sched; /* the template */ int kflags; /* DN_ACTIVE */ int64_t credit; /* bits I can transmit (more or less). */ uint64_t sched_time; /* time link was scheduled in ready_heap */ uint64_t idle_time; /* start of scheduler instance idle time */ /* q_count is the number of queues that this instance is using. * The counter is incremented or decremented when * a reference from the queue is created or deleted. * It is used to make sure that a scheduler instance can be safely * deleted by the drain routine. See notes below. */ int q_count; }; /* * NOTE about object drain. * The system will automatically (XXX check when) drain queues and * scheduler instances when they are idle. * A queue is idle when it has no packets; an instance is idle when * it is not in the evheap heap, and the corresponding delay line is empty. * A queue can be safely deleted when it is idle because of the scheduler * function xxx_free_queue() will remove any references to it. * An instance can be only deleted when no queues reference it. To be sure * of that, a counter (q_count) stores the number of queues that are pointing * to the instance. * * XXX * Order of scan: * - take all flowset in a bucket for the flowset hash table * - take all queues in a bucket for the flowset * - increment the queue bucket * - scan next flowset bucket * Nothing is done if a bucket contains no entries. * * The same schema is used for sceduler instances */ /* kernel-side flags. Linux has DN_DELETE in fcntl.h */ enum { /* 1 and 2 are reserved for the SCAN flags */ DN_DESTROY = 0x0004, /* destroy */ DN_DELETE_FS = 0x0008, /* destroy flowset */ DN_DETACH = 0x0010, DN_ACTIVE = 0x0020, /* object is in evheap */ DN_F_DLINE = 0x0040, /* object is a delay line */ DN_DEL_SAFE = 0x0080, /* delete a queue only if no longer needed * by scheduler */ DN_QHT_IS_Q = 0x0100, /* in flowset, qht is a single queue */ }; +/* + * Packets processed by dummynet have an mbuf tag associated with + * them that carries their dummynet state. + * Outside dummynet, only the 'rule' field is relevant, and it must + * be at the beginning of the structure. + */ +struct dn_pkt_tag { + struct ipfw_rule_ref rule; /* matching rule */ + + /* second part, dummynet specific */ + int dn_dir; /* action when packet comes out.*/ + /* see ip_fw_private.h */ + uint64_t output_time; /* when the pkt is due for delivery*/ + struct ifnet *ifp; /* interface, for ip_output */ + struct _ip6dn_args ip6opt; /* XXX ipv6 options */ + uint16_t iphdr_off; /* IP header offset for mtodo() */ +}; + extern struct dn_parms dn_cfg; //VNET_DECLARE(struct dn_parms, _base_dn_cfg); //#define dn_cfg VNET(_base_dn_cfg) int dummynet_io(struct mbuf **, int , struct ip_fw_args *); void dummynet_task(void *context, int pending); void dn_reschedule(void); +struct dn_pkt_tag * dn_tag_get(struct mbuf *m); struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *, struct ipfw_flow_id *); struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *); /* * copy_range is a template for requests for ranges of pipes/queues/scheds. * The number of ranges is variable and can be derived by o.len. * As a default, we use a small number of entries so that the struct * fits easily on the stack and is sufficient for most common requests. */ #define DEFAULT_RANGES 5 struct copy_range { struct dn_id o; uint32_t r[ 2 * DEFAULT_RANGES ]; }; struct copy_args { char **start; char *end; int flags; int type; struct copy_range *extra; /* extra filtering */ }; struct sockopt; int ip_dummynet_compat(struct sockopt *sopt); int dummynet_get(struct sockopt *sopt, void **compat); int dn_c_copy_q (void *_ni, void *arg); int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq); int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq); int dn_compat_copy_queue(struct copy_args *a, void *_o); int dn_compat_copy_pipe(struct copy_args *a, void *_o); int copy_data_helper_compat(void *_o, void *_arg); int dn_compat_calc_size(void); int do_config(void *p, int l); /* function to drain idle object */ void dn_drain_scheduler(void); void dn_drain_queue(void); #ifdef NEW_AQM int ecn_mark(struct mbuf* m); /* moved from ip_dn_io.c to here to be available for AQMs modules*/ static inline void mq_append(struct mq *q, struct mbuf *m) { #ifdef USERSPACE // buffers from netmap need to be copied // XXX note that the routine is not expected to fail ND("append %p to %p", m, q); if (m->m_flags & M_STACK) { struct mbuf *m_new; void *p; int l, ofs; ofs = m->m_data - m->__m_extbuf; // XXX allocate MGETHDR(m_new, M_NOWAIT, MT_DATA); ND("*** WARNING, volatile buf %p ext %p %d dofs %d m_new %p", m, m->__m_extbuf, m->__m_extlen, ofs, m_new); p = m_new->__m_extbuf; /* new pointer */ l = m_new->__m_extlen; /* new len */ if (l <= m->__m_extlen) { panic("extlen too large"); } *m_new = *m; // copy m_new->m_flags &= ~M_STACK; m_new->__m_extbuf = p; // point to new buffer _pkt_copy(m->__m_extbuf, p, m->__m_extlen); m_new->m_data = p + ofs; m = m_new; } #endif /* USERSPACE */ if (q->head == NULL) q->head = m; else q->tail->m_nextpkt = m; q->count++; q->tail = m; m->m_nextpkt = NULL; } #endif /* NEW_AQM */ #endif /* _IP_DN_PRIVATE_H */ Index: stable/11 =================================================================== --- stable/11 (revision 325729) +++ stable/11 (revision 325730) Property changes on: stable/11 ___________________________________________________________________ Modified: svn:mergeinfo ## -0,0 +0,1 ## Merged /head:r325008