DPDK  23.07.0
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
9 extern "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
36 struct rte_pie_params {
37  uint16_t qdelay_ref;
38  uint16_t dp_update_interval;
39  uint16_t max_burst;
40  uint16_t tailq_th;
41 };
42 
46 struct rte_pie_config {
47  uint64_t qdelay_ref;
48  uint64_t dp_update_interval;
49  uint64_t max_burst;
50  uint16_t tailq_th;
51 };
52 
56 struct rte_pie {
57  uint16_t active;
58  uint16_t in_measurement;
59  uint32_t departed_bytes_count;
60  uint64_t start_measurement;
61  uint64_t last_measurement;
62  uint64_t qlen;
63  uint64_t qlen_bytes;
64  uint64_t avg_dq_time;
65  uint32_t burst_allowance;
66  uint64_t qdelay_old;
67  double drop_prob;
68  double accu_prob;
69 };
70 
80 int
81 __rte_experimental
82 rte_pie_rt_data_init(struct rte_pie *pie);
83 
97 int
98 __rte_experimental
99 rte_pie_config_init(struct rte_pie_config *pie_cfg,
100  const uint16_t qdelay_ref,
101  const uint16_t dp_update_interval,
102  const uint16_t max_burst,
103  const uint16_t tailq_th);
104 
118 static int
119 __rte_experimental
120 rte_pie_enqueue_empty(const struct rte_pie_config *pie_cfg,
121  struct rte_pie *pie,
122  uint32_t pkt_len)
123 {
124  RTE_ASSERT(pkt_len != 0);
125 
126  /* Update the PIE qlen parameter */
127  pie->qlen++;
128  pie->qlen_bytes += pkt_len;
129 
133  if ((pie->active == 1) &&
134  (pie->qlen < (pie_cfg->tailq_th * 0.1))) {
135  pie->active = 0;
136  pie->in_measurement = 0;
137  }
138 
139  return 0;
140 }
141 
150 static void
151 __rte_experimental
152 _calc_drop_probability(const struct rte_pie_config *pie_cfg,
153  struct rte_pie *pie, uint64_t time)
154 {
155  uint64_t qdelay_ref = pie_cfg->qdelay_ref;
156 
157  /* Note: can be implemented using integer multiply.
158  * DQ_THRESHOLD is power of 2 value.
159  */
160  uint64_t current_qdelay = pie->qlen * (pie->avg_dq_time >> 14);
161 
162  double p = RTE_ALPHA * (current_qdelay - qdelay_ref) +
163  RTE_BETA * (current_qdelay - pie->qdelay_old);
164 
165  if (pie->drop_prob < 0.000001)
166  p = p * 0.00048828125; /* (1/2048) = 0.00048828125 */
167  else if (pie->drop_prob < 0.00001)
168  p = p * 0.001953125; /* (1/512) = 0.001953125 */
169  else if (pie->drop_prob < 0.0001)
170  p = p * 0.0078125; /* (1/128) = 0.0078125 */
171  else if (pie->drop_prob < 0.001)
172  p = p * 0.03125; /* (1/32) = 0.03125 */
173  else if (pie->drop_prob < 0.01)
174  p = p * 0.125; /* (1/8) = 0.125 */
175  else if (pie->drop_prob < 0.1)
176  p = p * 0.5; /* (1/2) = 0.5 */
177 
178  if (pie->drop_prob >= 0.1 && p > 0.02)
179  p = 0.02;
180 
181  pie->drop_prob += p;
182 
183  double qdelay = qdelay_ref * 0.5;
184 
185  /* Exponentially decay drop prob when congestion goes away */
186  if ((double)current_qdelay < qdelay && pie->qdelay_old < qdelay)
187  pie->drop_prob *= 0.98; /* 1 - 1/64 is sufficient */
188 
189  /* Bound drop probability */
190  if (pie->drop_prob < 0)
191  pie->drop_prob = 0;
192  if (pie->drop_prob > 1)
193  pie->drop_prob = 1;
194 
195  pie->qdelay_old = current_qdelay;
196  pie->last_measurement = time;
197 
198  uint64_t burst_allowance = pie->burst_allowance - pie_cfg->dp_update_interval;
199 
200  pie->burst_allowance = (burst_allowance > 0) ? burst_allowance : 0;
201 }
202 
214 static inline int
215 __rte_experimental
216 _rte_pie_drop(const struct rte_pie_config *pie_cfg,
217  struct rte_pie *pie)
218 {
219  uint64_t qdelay = pie_cfg->qdelay_ref / 2;
220 
221  /* PIE is active but the queue is not congested: return 0 */
222  if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
223  (pie->qlen <= (pie_cfg->tailq_th * 0.1)))
224  return 0;
225 
226  if (pie->drop_prob == 0)
227  pie->accu_prob = 0;
228 
229  /* For practical reasons, drop probability can be further scaled according
230  * to packet size, but one needs to set a bound to avoid unnecessary bias
231  * Random drop
232  */
233  pie->accu_prob += pie->drop_prob;
234 
235  if (pie->accu_prob < 0.85)
236  return 0;
237 
238  if (pie->accu_prob >= 8.5)
239  return 1;
240 
241  if (rte_drand() < pie->drop_prob) {
242  pie->accu_prob = 0;
243  return 1;
244  }
245 
246  /* No drop */
247  return 0;
248 }
249 
263 static inline int
264 __rte_experimental
265 rte_pie_enqueue_nonempty(const struct rte_pie_config *pie_cfg,
266  struct rte_pie *pie,
267  uint32_t pkt_len,
268  const uint64_t time)
269 {
270  /* Check queue space against the tail drop threshold */
271  if (pie->qlen >= pie_cfg->tailq_th) {
272 
273  pie->accu_prob = 0;
274  return 1;
275  }
276 
277  if (pie->active) {
278  /* Update drop probability after certain interval */
279  if ((time - pie->last_measurement) >= pie_cfg->dp_update_interval)
280  _calc_drop_probability(pie_cfg, pie, time);
281 
282  /* Decide whether packet to be dropped or enqueued */
283  if (_rte_pie_drop(pie_cfg, pie) && pie->burst_allowance == 0)
284  return 2;
285  }
286 
287  /* When queue occupancy is over a certain threshold, turn on PIE */
288  if ((pie->active == 0) &&
289  (pie->qlen >= (pie_cfg->tailq_th * 0.1))) {
290  pie->active = 1;
291  pie->qdelay_old = 0;
292  pie->drop_prob = 0;
293  pie->in_measurement = 1;
294  pie->departed_bytes_count = 0;
295  pie->avg_dq_time = 0;
296  pie->last_measurement = time;
297  pie->burst_allowance = pie_cfg->max_burst;
298  pie->accu_prob = 0;
299  pie->start_measurement = time;
300  }
301 
302  /* when queue has been idle for a while, turn off PIE and Reset counters */
303  if (pie->active == 1 &&
304  pie->qlen < (pie_cfg->tailq_th * 0.1)) {
305  pie->active = 0;
306  pie->in_measurement = 0;
307  }
308 
309  /* Update PIE qlen parameter */
310  pie->qlen++;
311  pie->qlen_bytes += pkt_len;
312 
313  /* No drop */
314  return 0;
315 }
316 
331 static inline int
332 __rte_experimental
333 rte_pie_enqueue(const struct rte_pie_config *pie_cfg,
334  struct rte_pie *pie,
335  const unsigned int qlen,
336  uint32_t pkt_len,
337  const uint64_t time)
338 {
339  RTE_ASSERT(pie_cfg != NULL);
340  RTE_ASSERT(pie != NULL);
341 
342  if (qlen != 0)
343  return rte_pie_enqueue_nonempty(pie_cfg, pie, pkt_len, time);
344  else
345  return rte_pie_enqueue_empty(pie_cfg, pie, pkt_len);
346 }
347 
356 static inline void
357 __rte_experimental
358 rte_pie_dequeue(struct rte_pie *pie,
359  uint32_t pkt_len,
360  uint64_t time)
361 {
362  /* Dequeue rate estimation */
363  if (pie->in_measurement) {
364  pie->departed_bytes_count += pkt_len;
365 
366  /* Start a new measurement cycle when enough packets */
368  uint64_t dq_time = time - pie->start_measurement;
369 
370  if (pie->avg_dq_time == 0)
371  pie->avg_dq_time = dq_time;
372  else
373  pie->avg_dq_time = dq_time * RTE_DQ_WEIGHT + pie->avg_dq_time
374  * (1 - RTE_DQ_WEIGHT);
375 
376  pie->in_measurement = 0;
377  }
378  }
379 
380  /* Start measurement cycle when enough data in the queue */
381  if ((pie->qlen_bytes >= RTE_DQ_THRESHOLD) && (pie->in_measurement == 0)) {
382  pie->in_measurement = 1;
383  pie->start_measurement = time;
384  pie->departed_bytes_count = 0;
385  }
386 }
387 
388 #ifdef __cplusplus
389 }
390 #endif
391 
392 #endif /* __RTE_PIE_H_INCLUDED__ */
uint64_t start_measurement
Definition: rte_pie.h:62
uint64_t qdelay_ref
Definition: rte_pie.h:49
uint32_t burst_allowance
Definition: rte_pie.h:67
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
uint16_t tailq_th
Definition: rte_pie.h:52
#define RTE_DQ_WEIGHT
Definition: rte_pie.h:29
uint64_t qdelay_old
Definition: rte_pie.h:68
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
uint64_t qlen_bytes
Definition: rte_pie.h:65
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 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
double drop_prob
Definition: rte_pie.h:69
#define RTE_DQ_THRESHOLD
Definition: rte_pie.h:24
uint16_t in_measurement
Definition: rte_pie.h:60
__rte_experimental double rte_drand(void)
double accu_prob
Definition: rte_pie.h:70
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
uint32_t departed_bytes_count
Definition: rte_pie.h:61
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
#define RTE_BETA
Definition: rte_pie.h:31
uint64_t dp_update_interval
Definition: rte_pie.h:50
uint64_t max_burst
Definition: rte_pie.h:51
uint16_t active
Definition: rte_pie.h:59
uint64_t avg_dq_time
Definition: rte_pie.h:66
#define RTE_ALPHA
Definition: rte_pie.h:30
uint64_t last_measurement
Definition: rte_pie.h:63
uint64_t qlen
Definition: rte_pie.h:64
int __rte_experimental rte_pie_rt_data_init(struct rte_pie *pie)
Initialises run-time data.
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