DPDK 22.11.5
rte_pie.h
Go to the documentation of this file.
1/* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2020 Intel Corporation
3 */
4
5#ifndef __RTE_PIE_H_INCLUDED__
6#define __RTE_PIE_H_INCLUDED__
7
8#ifdef __cplusplus
9extern "C" {
10#endif
11
17#include <stdint.h>
18
19#include <rte_compat.h>
20#include <rte_random.h>
21#include <rte_debug.h>
22#include <rte_cycles.h>
23
24#define RTE_DQ_THRESHOLD 16384
27#define RTE_DQ_WEIGHT 0.25
28#define RTE_ALPHA 0.125
29#define RTE_BETA 1.25
30#define RTE_RAND_MAX ~0LLU
38 uint16_t qdelay_ref;
40 uint16_t max_burst;
41 uint16_t tailq_th;
42};
43
49 uint64_t qdelay_ref;
51 uint64_t max_burst;
52 uint16_t tailq_th;
53};
54
58struct rte_pie {
59 uint16_t active;
60 uint16_t in_measurement;
64 uint64_t qlen;
65 uint64_t qlen_bytes;
66 uint64_t avg_dq_time;
67 uint32_t burst_allowance;
68 uint64_t qdelay_old;
69 double drop_prob;
70 double accu_prob;
71};
72
82int
83__rte_experimental
85
99int
100__rte_experimental
102 const uint16_t qdelay_ref,
103 const uint16_t dp_update_interval,
104 const uint16_t max_burst,
105 const uint16_t tailq_th);
106
120static int
121__rte_experimental
123 struct rte_pie *pie,
124 uint32_t pkt_len)
125{
126 RTE_ASSERT(pkt_len != 0);
127
128 /* Update the PIE qlen parameter */
129 pie->qlen++;
130 pie->qlen_bytes += pkt_len;
131
135 if ((pie->active == 1) &&
136 (pie->qlen < (pie_cfg->tailq_th * 0.1))) {
137 pie->active = 0;
138 pie->in_measurement = 0;
139 }
140
141 return 0;
142}
143
152static void
153__rte_experimental
155 struct rte_pie *pie, uint64_t time)
156{
157 uint64_t qdelay_ref = pie_cfg->qdelay_ref;
158
159 /* Note: can be implemented using integer multiply.
160 * DQ_THRESHOLD is power of 2 value.
161 */
162 uint64_t current_qdelay = pie->qlen * (pie->avg_dq_time >> 14);
163
164 double p = RTE_ALPHA * (current_qdelay - qdelay_ref) +
165 RTE_BETA * (current_qdelay - pie->qdelay_old);
166
167 if (pie->drop_prob < 0.000001)
168 p = p * 0.00048828125; /* (1/2048) = 0.00048828125 */
169 else if (pie->drop_prob < 0.00001)
170 p = p * 0.001953125; /* (1/512) = 0.001953125 */
171 else if (pie->drop_prob < 0.0001)
172 p = p * 0.0078125; /* (1/128) = 0.0078125 */
173 else if (pie->drop_prob < 0.001)
174 p = p * 0.03125; /* (1/32) = 0.03125 */
175 else if (pie->drop_prob < 0.01)
176 p = p * 0.125; /* (1/8) = 0.125 */
177 else if (pie->drop_prob < 0.1)
178 p = p * 0.5; /* (1/2) = 0.5 */
179
180 if (pie->drop_prob >= 0.1 && p > 0.02)
181 p = 0.02;
182
183 pie->drop_prob += p;
184
185 double qdelay = qdelay_ref * 0.5;
186
187 /* Exponentially decay drop prob when congestion goes away */
188 if ((double)current_qdelay < qdelay && pie->qdelay_old < qdelay)
189 pie->drop_prob *= 0.98; /* 1 - 1/64 is sufficient */
190
191 /* Bound drop probability */
192 if (pie->drop_prob < 0)
193 pie->drop_prob = 0;
194 if (pie->drop_prob > 1)
195 pie->drop_prob = 1;
196
197 pie->qdelay_old = current_qdelay;
198 pie->last_measurement = time;
199
200 uint64_t burst_allowance = pie->burst_allowance - pie_cfg->dp_update_interval;
201
202 pie->burst_allowance = (burst_allowance > 0) ? burst_allowance : 0;
203}
204
216static inline int
217__rte_experimental
218_rte_pie_drop(const struct rte_pie_config *pie_cfg,
219 struct rte_pie *pie)
220{
221 uint64_t qdelay = pie_cfg->qdelay_ref / 2;
222
223 /* PIE is active but the queue is not congested: return 0 */
224 if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
225 (pie->qlen <= (pie_cfg->tailq_th * 0.1)))
226 return 0;
227
228 if (pie->drop_prob == 0)
229 pie->accu_prob = 0;
230
231 /* For practical reasons, drop probability can be further scaled according
232 * to packet size, but one needs to set a bound to avoid unnecessary bias
233 * Random drop
234 */
235 pie->accu_prob += pie->drop_prob;
236
237 if (pie->accu_prob < 0.85)
238 return 0;
239
240 if (pie->accu_prob >= 8.5)
241 return 1;
242
243 if (rte_drand() < pie->drop_prob) {
244 pie->accu_prob = 0;
245 return 1;
246 }
247
248 /* No drop */
249 return 0;
250}
251
265static inline int
266__rte_experimental
268 struct rte_pie *pie,
269 uint32_t pkt_len,
270 const uint64_t time)
271{
272 /* Check queue space against the tail drop threshold */
273 if (pie->qlen >= pie_cfg->tailq_th) {
274
275 pie->accu_prob = 0;
276 return 1;
277 }
278
279 if (pie->active) {
280 /* Update drop probability after certain interval */
281 if ((time - pie->last_measurement) >= pie_cfg->dp_update_interval)
282 _calc_drop_probability(pie_cfg, pie, time);
283
284 /* Decide whether packet to be dropped or enqueued */
285 if (_rte_pie_drop(pie_cfg, pie) && pie->burst_allowance == 0)
286 return 2;
287 }
288
289 /* When queue occupancy is over a certain threshold, turn on PIE */
290 if ((pie->active == 0) &&
291 (pie->qlen >= (pie_cfg->tailq_th * 0.1))) {
292 pie->active = 1;
293 pie->qdelay_old = 0;
294 pie->drop_prob = 0;
295 pie->in_measurement = 1;
296 pie->departed_bytes_count = 0;
297 pie->avg_dq_time = 0;
298 pie->last_measurement = time;
299 pie->burst_allowance = pie_cfg->max_burst;
300 pie->accu_prob = 0;
301 pie->start_measurement = time;
302 }
303
304 /* when queue has been idle for a while, turn off PIE and Reset counters */
305 if (pie->active == 1 &&
306 pie->qlen < (pie_cfg->tailq_th * 0.1)) {
307 pie->active = 0;
308 pie->in_measurement = 0;
309 }
310
311 /* Update PIE qlen parameter */
312 pie->qlen++;
313 pie->qlen_bytes += pkt_len;
314
315 /* No drop */
316 return 0;
317}
318
333static inline int
334__rte_experimental
335rte_pie_enqueue(const struct rte_pie_config *pie_cfg,
336 struct rte_pie *pie,
337 const unsigned int qlen,
338 uint32_t pkt_len,
339 const uint64_t time)
340{
341 RTE_ASSERT(pie_cfg != NULL);
342 RTE_ASSERT(pie != NULL);
343
344 if (qlen != 0)
345 return rte_pie_enqueue_nonempty(pie_cfg, pie, pkt_len, time);
346 else
347 return rte_pie_enqueue_empty(pie_cfg, pie, pkt_len);
348}
349
358static inline void
359__rte_experimental
361 uint32_t pkt_len,
362 uint64_t time)
363{
364 /* Dequeue rate estimation */
365 if (pie->in_measurement) {
366 pie->departed_bytes_count += pkt_len;
367
368 /* Start a new measurement cycle when enough packets */
370 uint64_t dq_time = time - pie->start_measurement;
371
372 if (pie->avg_dq_time == 0)
373 pie->avg_dq_time = dq_time;
374 else
375 pie->avg_dq_time = dq_time * RTE_DQ_WEIGHT + pie->avg_dq_time
376 * (1 - RTE_DQ_WEIGHT);
377
378 pie->in_measurement = 0;
379 }
380 }
381
382 /* Start measurement cycle when enough data in the queue */
383 if ((pie->qlen_bytes >= RTE_DQ_THRESHOLD) && (pie->in_measurement == 0)) {
384 pie->in_measurement = 1;
385 pie->start_measurement = time;
386 pie->departed_bytes_count = 0;
387 }
388}
389
390#ifdef __cplusplus
391}
392#endif
393
394#endif /* __RTE_PIE_H_INCLUDED__ */
int __rte_experimental rte_pie_config_init(struct rte_pie_config *pie_cfg, const uint16_t qdelay_ref, const uint16_t dp_update_interval, const uint16_t max_burst, const uint16_t tailq_th)
Configures a single PIE configuration parameter structure.
static void __rte_experimental rte_pie_dequeue(struct rte_pie *pie, uint32_t pkt_len, uint64_t time)
PIE rate estimation method Called on each packet departure.
Definition: rte_pie.h:360
static int __rte_experimental rte_pie_enqueue_empty(const struct rte_pie_config *pie_cfg, struct rte_pie *pie, uint32_t pkt_len)
Decides packet enqueue when queue is empty.
Definition: rte_pie.h:122
static int __rte_experimental rte_pie_enqueue(const struct rte_pie_config *pie_cfg, struct rte_pie *pie, const unsigned int qlen, uint32_t pkt_len, const uint64_t time)
Decides if new packet should be enqueued or dropped Updates run time data and gives verdict whether t...
Definition: rte_pie.h:335
#define RTE_ALPHA
Definition: rte_pie.h:28
#define RTE_DQ_THRESHOLD
Definition: rte_pie.h:24
static void __rte_experimental _calc_drop_probability(const struct rte_pie_config *pie_cfg, struct rte_pie *pie, uint64_t time)
make a decision to drop or enqueue a packet based on probability criteria
Definition: rte_pie.h:154
#define RTE_BETA
Definition: rte_pie.h:29
#define RTE_DQ_WEIGHT
Definition: rte_pie.h:27
static int __rte_experimental rte_pie_enqueue_nonempty(const struct rte_pie_config *pie_cfg, struct rte_pie *pie, uint32_t pkt_len, const uint64_t time)
Decides if new packet should be enqueued or dropped for non-empty queue.
Definition: rte_pie.h:267
static int __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie)
make a decision to drop or enqueue a packet based on probability criteria
Definition: rte_pie.h:218
int __rte_experimental rte_pie_rt_data_init(struct rte_pie *pie)
Initialises run-time data.
__rte_experimental double rte_drand(void)
uint16_t tailq_th
Definition: rte_pie.h:52
uint64_t qdelay_ref
Definition: rte_pie.h:49
uint64_t max_burst
Definition: rte_pie.h:51
uint64_t dp_update_interval
Definition: rte_pie.h:50
uint16_t max_burst
Definition: rte_pie.h:40
uint16_t dp_update_interval
Definition: rte_pie.h:39
uint16_t tailq_th
Definition: rte_pie.h:41
uint16_t qdelay_ref
Definition: rte_pie.h:38
uint16_t in_measurement
Definition: rte_pie.h:60
uint32_t departed_bytes_count
Definition: rte_pie.h:61
uint64_t last_measurement
Definition: rte_pie.h:63
uint64_t qlen
Definition: rte_pie.h:64
uint64_t avg_dq_time
Definition: rte_pie.h:66
uint32_t burst_allowance
Definition: rte_pie.h:67
double accu_prob
Definition: rte_pie.h:70
uint64_t start_measurement
Definition: rte_pie.h:62
double drop_prob
Definition: rte_pie.h:69
uint64_t qlen_bytes
Definition: rte_pie.h:65
uint64_t qdelay_old
Definition: rte_pie.h:68
uint16_t active
Definition: rte_pie.h:59