1300779Struckman/* 2300779Struckman * Codel - The Controlled-Delay Active Queue Management algorithm. 3300779Struckman * 4300779Struckman * $FreeBSD$ 5300779Struckman * 6300779Struckman * Copyright (C) 2016 Centre for Advanced Internet Architectures, 7300779Struckman * Swinburne University of Technology, Melbourne, Australia. 8300779Struckman * Portions of this code were made possible in part by a gift from 9300779Struckman * The Comcast Innovation Fund. 10300779Struckman * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au> 11300779Struckman * 12300779Struckman * Copyright (C) 2011-2014 Kathleen Nichols <nichols@pollere.com>. 13300779Struckman * 14300779Struckman * Redistribution and use in source and binary forms, with or without 15300779Struckman * modification, are permitted provided that the following conditions 16300779Struckman * are met: 17300779Struckman * 18300779Struckman * o Redistributions of source code must retain the above copyright 19300779Struckman * notice, this list of conditions, and the following disclaimer, 20300779Struckman * without modification. 21300779Struckman * 22300779Struckman * o Redistributions in binary form must reproduce the above copyright 23300779Struckman * notice, this list of conditions and the following disclaimer in 24300779Struckman * the documentation and/or other materials provided with the 25300779Struckman * distribution. 26300779Struckman * 27300779Struckman * o The names of the authors may not be used to endorse or promote 28300779Struckman * products derived from this software without specific prior written 29300779Struckman * permission. 30300779Struckman * 31300779Struckman * Alternatively, provided that this notice is retained in full, this 32300779Struckman * software may be distributed under the terms of the GNU General Public 33300779Struckman * License ("GPL") version 2, in which case the provisions of the GPL 34300779Struckman * apply INSTEAD OF those given above. 35300779Struckman 36300779Struckman * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 37300779Struckman * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 38300779Struckman * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 39300779Struckman * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 40300779Struckman * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41300779Struckman * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 42300779Struckman * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 43300779Struckman * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 44300779Struckman * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 45300779Struckman * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 46300779Struckman * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 47300779Struckman */ 48300779Struckman 49300779Struckman#ifndef _IP_DN_SCHED_FQ_CODEL_HELPER_H 50300779Struckman#define _IP_DN_SCHED_FQ_CODEL_HELPER_H 51300779Struckman 52300779Struckman__inline static struct mbuf * 53300779Struckmanfqc_dodequeue(struct fq_codel_flow *q, aqm_time_t now, uint16_t *ok_to_drop, 54300779Struckman struct fq_codel_si *si) 55300779Struckman{ 56300779Struckman struct mbuf * m; 57300779Struckman struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1); 58300779Struckman aqm_time_t pkt_ts, sojourn_time; 59300779Struckman 60300779Struckman *ok_to_drop = 0; 61300779Struckman m = fq_codel_extract_head(q, &pkt_ts, si); 62300779Struckman 63300779Struckman if (m == NULL) { 64300779Struckman /*queue is empty - we can't be above target*/ 65300779Struckman q->cst.first_above_time= 0; 66300779Struckman return m; 67300779Struckman } 68300779Struckman 69300779Struckman /* To span a large range of bandwidths, CoDel runs two 70300779Struckman * different AQMs in parallel. One is sojourn-time-based 71300779Struckman * and takes effect when the time to send an MTU-sized 72300779Struckman * packet is less than target. The 1st term of the "if" 73300779Struckman * below does this. The other is backlog-based and takes 74300779Struckman * effect when the time to send an MTU-sized packet is >= 75300779Struckman * target. The goal here is to keep the output link 76300779Struckman * utilization high by never allowing the queue to get 77300779Struckman * smaller than the amount that arrives in a typical 78300779Struckman * interarrival time (MTU-sized packets arriving spaced 79300779Struckman * by the amount of time it takes to send such a packet on 80300779Struckman * the bottleneck). The 2nd term of the "if" does this. 81300779Struckman */ 82300779Struckman sojourn_time = now - pkt_ts; 83300779Struckman if (sojourn_time < schk->cfg.ccfg.target || q->stats.len_bytes <= q->cst.maxpkt_size) { 84300779Struckman /* went below - stay below for at least interval */ 85300779Struckman q->cst.first_above_time = 0; 86300779Struckman } else { 87300779Struckman if (q->cst.first_above_time == 0) { 88300779Struckman /* just went above from below. if still above at 89300779Struckman * first_above_time, will say it's ok to drop. */ 90300779Struckman q->cst.first_above_time = now + schk->cfg.ccfg.interval; 91300779Struckman } else if (now >= q->cst.first_above_time) { 92300779Struckman *ok_to_drop = 1; 93300779Struckman } 94300779Struckman } 95300779Struckman return m; 96300779Struckman} 97300779Struckman 98300779Struckman/* Codel dequeue function */ 99300779Struckman__inline static struct mbuf * 100300779Struckmanfqc_codel_dequeue(struct fq_codel_flow *q, struct fq_codel_si *si) 101300779Struckman{ 102300779Struckman struct mbuf *m; 103300779Struckman struct dn_aqm_codel_parms *cprms; 104300779Struckman struct codel_status *cst; 105300779Struckman aqm_time_t now; 106300779Struckman uint16_t ok_to_drop; 107300779Struckman struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1); 108300779Struckman 109300779Struckman cst = &q->cst; 110300779Struckman cprms = &schk->cfg.ccfg; 111300779Struckman 112300779Struckman now = AQM_UNOW; 113300779Struckman m = fqc_dodequeue(q, now, &ok_to_drop, si); 114300779Struckman 115300779Struckman if (cst->dropping) { 116300779Struckman if (!ok_to_drop) { 117300779Struckman /* sojourn time below target - leave dropping state */ 118300779Struckman cst->dropping = false; 119300779Struckman } 120300779Struckman 121300779Struckman /* Time for the next drop. Drop current packet and dequeue 122300779Struckman * next. If the dequeue doesn't take us out of dropping 123300779Struckman * state, schedule the next drop. A large backlog might 124300779Struckman * result in drop rates so high that the next drop should 125300779Struckman * happen now, hence the 'while' loop. 126300779Struckman */ 127300779Struckman while (now >= cst->drop_next_time && cst->dropping) { 128300779Struckman 129300779Struckman /* mark the packet */ 130300779Struckman if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) { 131300779Struckman cst->count++; 132300779Struckman /* schedule the next mark. */ 133300779Struckman cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time); 134300779Struckman return m; 135300779Struckman } 136300779Struckman 137300779Struckman /* drop the packet */ 138300779Struckman fq_update_stats(q, si, 0, 1); 139300779Struckman m_freem(m); 140300779Struckman m = fqc_dodequeue(q, now, &ok_to_drop, si); 141300779Struckman 142300779Struckman if (!ok_to_drop) { 143300779Struckman /* leave dropping state */ 144300779Struckman cst->dropping = false; 145300779Struckman } else { 146300779Struckman cst->count++; 147300779Struckman /* schedule the next drop. */ 148300779Struckman cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time); 149300779Struckman } 150300779Struckman } 151300779Struckman /* If we get here we're not in dropping state. The 'ok_to_drop' 152300779Struckman * return from dodequeue means that the sojourn time has been 153300779Struckman * above 'target' for 'interval' so enter dropping state. 154300779Struckman */ 155300779Struckman } else if (ok_to_drop) { 156300779Struckman 157300779Struckman /* if ECN option is disabled or the packet cannot be marked, 158300779Struckman * drop the packet and extract another. 159300779Struckman */ 160300779Struckman if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) { 161300779Struckman fq_update_stats(q, si, 0, 1); 162300779Struckman m_freem(m); 163300779Struckman m = fqc_dodequeue(q, now, &ok_to_drop,si); 164300779Struckman } 165300779Struckman 166300779Struckman cst->dropping = true; 167300779Struckman 168300779Struckman /* If min went above target close to when it last went 169300779Struckman * below, assume that the drop rate that controlled the 170300779Struckman * queue on the last cycle is a good starting point to 171300779Struckman * control it now. ('drop_next' will be at most 'interval' 172300779Struckman * later than the time of the last drop so 'now - drop_next' 173300779Struckman * is a good approximation of the time from the last drop 174300779Struckman * until now.) 175300779Struckman */ 176300779Struckman cst->count = (cst->count > 2 && ((aqm_stime_t)now - 177300779Struckman (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? cst->count - 2 : 1; 178300779Struckman 179300779Struckman /* we don't have to set initial guess for Newton's method isqrt as 180300779Struckman * we initilaize isqrt in control_law function when count == 1 */ 181300779Struckman cst->drop_next_time = control_law(cst, cprms, now); 182300779Struckman } 183300779Struckman 184300779Struckman return m; 185300779Struckman} 186300779Struckman 187300779Struckman#endif 188