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
fq_update_stats(struct fq_codel_flow * q,struct fq_codel_si * si,int len,int drop)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 *
fq_codel_extract_head(struct fq_codel_flow * q,aqm_time_t * pkt_ts,struct fq_codel_si * si)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