1 /*- 2 * Copyright (C) 2016 Centre for Advanced Internet Architectures, 3 * Swinburne University of Technology, Melbourne, Australia. 4 * Portions of this code were made possible in part by a gift from 5 * The Comcast Innovation Fund. 6 * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au> 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 /* 31 * FQ_Codel Structures and helper functions 32 * 33 * $FreeBSD$ 34 */ 35 36 #ifndef _IP_DN_SCHED_FQ_CODEL_H 37 #define _IP_DN_SCHED_FQ_CODEL_H 38 39 /* list of queues */ 40 STAILQ_HEAD(fq_codel_list, fq_codel_flow); 41 42 /* fq_codel parameters including codel */ 43 struct dn_sch_fq_codel_parms { 44 struct dn_aqm_codel_parms ccfg; /* CoDel Parameters */ 45 /* FQ_CODEL Parameters */ 46 uint32_t flows_cnt; /* number of flows */ 47 uint32_t limit; /* hard limit of fq_codel queue size*/ 48 uint32_t quantum; 49 }; /* defaults */ 50 51 /* flow (sub-queue) stats */ 52 struct flow_stats { 53 uint64_t tot_pkts; /* statistics counters */ 54 uint64_t tot_bytes; 55 uint32_t length; /* Queue length, in packets */ 56 uint32_t len_bytes; /* Queue length, in bytes */ 57 uint32_t drops; 58 }; 59 60 /* A flow of packets (sub-queue).*/ 61 struct fq_codel_flow { 62 struct mq mq; /* list of packets */ 63 struct flow_stats stats; /* statistics */ 64 int deficit; 65 int active; /* 1: flow is active (in a list) */ 66 struct codel_status cst; 67 STAILQ_ENTRY(fq_codel_flow) flowchain; 68 }; 69 70 /* extra fq_codel scheduler configurations */ 71 struct fq_codel_schk { 72 struct dn_sch_fq_codel_parms cfg; 73 }; 74 75 /* fq_codel scheduler instance */ 76 struct fq_codel_si { 77 struct dn_sch_inst _si; /* standard scheduler instance */ 78 struct dn_queue main_q; /* main queue is after si directly */ 79 80 struct fq_codel_flow *flows; /* array of flows (queues) */ 81 uint32_t perturbation; /* random value */ 82 struct fq_codel_list newflows; /* list of new queues */ 83 struct fq_codel_list oldflows; /* list of old queues */ 84 }; 85 86 /* Helper function to update queue&main-queue and scheduler statistics. 87 * negative len + drop -> drop 88 * negative len -> dequeue 89 * positive len -> enqueue 90 * positive len + drop -> drop during enqueue 91 */ 92 __inline static void 93 fq_update_stats(struct fq_codel_flow *q, struct fq_codel_si *si, int len, 94 int drop) 95 { 96 int inc = 0; 97 98 if (len < 0) 99 inc = -1; 100 else if (len > 0) 101 inc = 1; 102 103 if (drop) { 104 si->main_q.ni.drops ++; 105 q->stats.drops ++; 106 si->_si.ni.drops ++; 107 V_dn_cfg.io_pkt_drop ++; 108 } 109 110 if (!drop || (drop && len < 0)) { 111 /* Update stats for the main queue */ 112 si->main_q.ni.length += inc; 113 si->main_q.ni.len_bytes += len; 114 115 /*update sub-queue stats */ 116 q->stats.length += inc; 117 q->stats.len_bytes += len; 118 119 /*update scheduler instance stats */ 120 si->_si.ni.length += inc; 121 si->_si.ni.len_bytes += len; 122 } 123 124 if (inc > 0) { 125 si->main_q.ni.tot_bytes += len; 126 si->main_q.ni.tot_pkts ++; 127 128 q->stats.tot_bytes +=len; 129 q->stats.tot_pkts++; 130 131 si->_si.ni.tot_bytes +=len; 132 si->_si.ni.tot_pkts ++; 133 } 134 135 } 136 137 /* extract the head of fq_codel sub-queue */ 138 __inline static struct mbuf * 139 fq_codel_extract_head(struct fq_codel_flow *q, aqm_time_t *pkt_ts, struct fq_codel_si *si) 140 { 141 struct mbuf *m; 142 143 next: m = q->mq.head; 144 if (m == NULL) 145 return m; 146 q->mq.head = m->m_nextpkt; 147 148 fq_update_stats(q, si, -m->m_pkthdr.len, 0); 149 150 if (si->main_q.ni.length == 0) /* queue is now idle */ 151 si->main_q.q_time = V_dn_cfg.curr_time; 152 153 /* extract packet timestamp*/ 154 struct m_tag *mtag; 155 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 156 if (mtag == NULL){ 157 D("timestamp tag is not found!"); 158 *pkt_ts = 0; 159 } else { 160 *pkt_ts = *(aqm_time_t *)(mtag + 1); 161 m_tag_delete(m,mtag); 162 } 163 if (m->m_pkthdr.rcvif != NULL && 164 __predict_false(m_rcvif_restore(m) == NULL)) { 165 m_freem(m); 166 goto next; 167 } 168 return m; 169 } 170 171 #endif 172