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 VNET_DECLARE(unsigned long, io_pkt_drop); 40 #define V_io_pkt_drop VNET(io_pkt_drop) 41 42 /* list of queues */ 43 STAILQ_HEAD(fq_codel_list, fq_codel_flow) ; 44 45 /* fq_codel parameters including codel */ 46 struct dn_sch_fq_codel_parms { 47 struct dn_aqm_codel_parms ccfg; /* CoDel Parameters */ 48 /* FQ_CODEL Parameters */ 49 uint32_t flows_cnt; /* number of flows */ 50 uint32_t limit; /* hard limit of fq_codel queue size*/ 51 uint32_t quantum; 52 }; /* defaults */ 53 54 /* flow (sub-queue) stats */ 55 struct flow_stats { 56 uint64_t tot_pkts; /* statistics counters */ 57 uint64_t tot_bytes; 58 uint32_t length; /* Queue length, in packets */ 59 uint32_t len_bytes; /* Queue length, in bytes */ 60 uint32_t drops; 61 }; 62 63 /* A flow of packets (sub-queue).*/ 64 struct fq_codel_flow { 65 struct mq mq; /* list of packets */ 66 struct flow_stats stats; /* statistics */ 67 int deficit; 68 int active; /* 1: flow is active (in a list) */ 69 struct codel_status cst; 70 STAILQ_ENTRY(fq_codel_flow) flowchain; 71 }; 72 73 /* extra fq_codel scheduler configurations */ 74 struct fq_codel_schk { 75 struct dn_sch_fq_codel_parms cfg; 76 }; 77 78 /* fq_codel scheduler instance */ 79 struct fq_codel_si { 80 struct dn_sch_inst _si; /* standard scheduler instance */ 81 struct dn_queue main_q; /* main queue is after si directly */ 82 83 struct fq_codel_flow *flows; /* array of flows (queues) */ 84 uint32_t perturbation; /* random value */ 85 struct fq_codel_list newflows; /* list of new queues */ 86 struct fq_codel_list oldflows; /* list of old queues */ 87 }; 88 89 /* Helper function to update queue&main-queue and scheduler statistics. 90 * negative len + drop -> drop 91 * negative len -> dequeue 92 * positive len -> enqueue 93 * positive len + drop -> drop during enqueue 94 */ 95 __inline static void 96 fq_update_stats(struct fq_codel_flow *q, struct fq_codel_si *si, int len, 97 int drop) 98 { 99 int inc = 0; 100 101 if (len < 0) 102 inc = -1; 103 else if (len > 0) 104 inc = 1; 105 106 if (drop) { 107 si->main_q.ni.drops ++; 108 q->stats.drops ++; 109 si->_si.ni.drops ++; 110 V_dn_cfg.io_pkt_drop ++; 111 } 112 113 if (!drop || (drop && len < 0)) { 114 /* Update stats for the main queue */ 115 si->main_q.ni.length += inc; 116 si->main_q.ni.len_bytes += len; 117 118 /*update sub-queue stats */ 119 q->stats.length += inc; 120 q->stats.len_bytes += len; 121 122 /*update scheduler instance stats */ 123 si->_si.ni.length += inc; 124 si->_si.ni.len_bytes += len; 125 } 126 127 if (inc > 0) { 128 si->main_q.ni.tot_bytes += len; 129 si->main_q.ni.tot_pkts ++; 130 131 q->stats.tot_bytes +=len; 132 q->stats.tot_pkts++; 133 134 si->_si.ni.tot_bytes +=len; 135 si->_si.ni.tot_pkts ++; 136 } 137 138 } 139 140 /* extract the head of fq_codel sub-queue */ 141 __inline static struct mbuf * 142 fq_codel_extract_head(struct fq_codel_flow *q, aqm_time_t *pkt_ts, struct fq_codel_si *si) 143 { 144 struct mbuf *m = q->mq.head; 145 146 if (m == NULL) 147 return m; 148 q->mq.head = m->m_nextpkt; 149 150 fq_update_stats(q, si, -m->m_pkthdr.len, 0); 151 152 if (si->main_q.ni.length == 0) /* queue is now idle */ 153 si->main_q.q_time = V_dn_cfg.curr_time; 154 155 /* extract packet timestamp*/ 156 struct m_tag *mtag; 157 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 158 if (mtag == NULL){ 159 D("timestamp tag is not found!"); 160 *pkt_ts = 0; 161 } else { 162 *pkt_ts = *(aqm_time_t *)(mtag + 1); 163 m_tag_delete(m,mtag); 164 } 165 166 return m; 167 } 168 169 #endif 170