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