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 | 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 = q->mq.head; |
---|
142 | |
---|
143 | if (m == NULL) |
---|
144 | return m; |
---|
145 | q->mq.head = m->m_nextpkt; |
---|
146 | |
---|
147 | fq_update_stats(q, si, -m->m_pkthdr.len, 0); |
---|
148 | |
---|
149 | if (si->main_q.ni.length == 0) /* queue is now idle */ |
---|
150 | si->main_q.q_time = dn_cfg.curr_time; |
---|
151 | |
---|
152 | /* extract packet timestamp*/ |
---|
153 | struct m_tag *mtag; |
---|
154 | mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); |
---|
155 | if (mtag == NULL){ |
---|
156 | D("timestamp tag is not found!"); |
---|
157 | *pkt_ts = 0; |
---|
158 | } else { |
---|
159 | *pkt_ts = *(aqm_time_t *)(mtag + 1); |
---|
160 | m_tag_delete(m,mtag); |
---|
161 | } |
---|
162 | |
---|
163 | return m; |
---|
164 | } |
---|
165 | |
---|
166 | |
---|
167 | #endif |
---|