DPDK  22.03.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_random.h>
20 #include <rte_debug.h>
21 #include <rte_cycles.h>
22 
23 #define RTE_DQ_THRESHOLD 16384
26 #define RTE_DQ_WEIGHT 0.25
27 #define RTE_ALPHA 0.125
28 #define RTE_BETA 1.25
29 #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 
47 struct rte_pie_config {
48  uint64_t qdelay_ref;
49  uint64_t dp_update_interval;
50  uint64_t max_burst;
51  uint16_t tailq_th;
52 };
53 
57 struct rte_pie {
58  uint16_t active;
59  uint16_t in_measurement;
60  uint32_t departed_bytes_count;
61  uint64_t start_measurement;
62  uint64_t last_measurement;
63  uint64_t qlen;
64  uint64_t qlen_bytes;
65  uint64_t avg_dq_time;
66  uint32_t burst_allowance;
67  uint64_t qdelay_old;
68  double drop_prob;
69  double accu_prob;
70 };
71 
81 int
82 __rte_experimental
83 rte_pie_rt_data_init(struct rte_pie *pie);
84 
98 int
99 __rte_experimental
100 rte_pie_config_init(struct rte_pie_config *pie_cfg,
101  const uint16_t qdelay_ref,
102  const uint16_t dp_update_interval,
103  const uint16_t max_burst,
104  const uint16_t tailq_th);
105 
119 static int
120 __rte_experimental
121 rte_pie_enqueue_empty(const struct rte_pie_config *pie_cfg,
122  struct rte_pie *pie,
123  uint32_t pkt_len)
124 {
125  RTE_ASSERT(pkt_len != 0);
126 
127  /* Update the PIE qlen parameter */
128  pie->qlen++;
129  pie->qlen_bytes += pkt_len;
130 
134  if ((pie->active == 1) &&
135  (pie->qlen < (pie_cfg->tailq_th * 0.1))) {
136  pie->active = 0;
137  pie->in_measurement = 0;
138  }
139 
140  return 0;
141 }
142 
151 static void
152 __rte_experimental
153 _calc_drop_probability(const struct rte_pie_config *pie_cfg,
154  struct rte_pie *pie, uint64_t time)
155 {
156  uint64_t qdelay_ref = pie_cfg->qdelay_ref;
157 
158  /* Note: can be implemented using integer multiply.
159  * DQ_THRESHOLD is power of 2 value.
160  */
161  uint64_t current_qdelay = pie->qlen * (pie->avg_dq_time >> 14);
162 
163  double p = RTE_ALPHA * (current_qdelay - qdelay_ref) +
164  RTE_BETA * (current_qdelay - pie->qdelay_old);
165 
166  if (pie->drop_prob < 0.000001)
167  p = p * 0.00048828125; /* (1/2048) = 0.00048828125 */
168  else if (pie->drop_prob < 0.00001)
169  p = p * 0.001953125; /* (1/512) = 0.001953125 */
170  else if (pie->drop_prob < 0.0001)
171  p = p * 0.0078125; /* (1/128) = 0.0078125 */
172  else if (pie->drop_prob < 0.001)
173  p = p * 0.03125; /* (1/32) = 0.03125 */
174  else if (pie->drop_prob < 0.01)
175  p = p * 0.125; /* (1/8) = 0.125 */
176  else if (pie->drop_prob < 0.1)
177  p = p * 0.5; /* (1/2) = 0.5 */
178 
179  if (pie->drop_prob >= 0.1 && p > 0.02)
180  p = 0.02;
181 
182  pie->drop_prob += p;
183 
184  double qdelay = qdelay_ref * 0.5;
185 
186  /* Exponentially decay drop prob when congestion goes away */
187  if ((double)current_qdelay < qdelay && pie->qdelay_old < qdelay)
188  pie->drop_prob *= 0.98; /* 1 - 1/64 is sufficient */
189 
190  /* Bound drop probability */
191  if (pie->drop_prob < 0)
192  pie->drop_prob = 0;
193  if (pie->drop_prob > 1)
194  pie->drop_prob = 1;
195 
196  pie->qdelay_old = current_qdelay;
197  pie->last_measurement = time;
198 
199  uint64_t burst_allowance = pie->burst_allowance - pie_cfg->dp_update_interval;
200 
201  pie->burst_allowance = (burst_allowance > 0) ? burst_allowance : 0;
202 }
203 
215 static inline int
216 __rte_experimental
217 _rte_pie_drop(const struct rte_pie_config *pie_cfg,
218  struct rte_pie *pie)
219 {
220  uint64_t rand_value;
221  double qdelay = pie_cfg->qdelay_ref * 0.5;
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  rand_value = rte_rand()/RTE_RAND_MAX;
244 
245  if ((double)rand_value < pie->drop_prob) {
246  pie->accu_prob = 0;
247  return 1;
248  }
249 
250  /* No drop */
251  return 0;
252 }
253 
267 static inline int
268 __rte_experimental
269 rte_pie_enqueue_nonempty(const struct rte_pie_config *pie_cfg,
270  struct rte_pie *pie,
271  uint32_t pkt_len,
272  const uint64_t time)
273 {
274  /* Check queue space against the tail drop threshold */
275  if (pie->qlen >= pie_cfg->tailq_th) {
276 
277  pie->accu_prob = 0;
278  return 1;
279  }
280 
281  if (pie->active) {
282  /* Update drop probability after certain interval */
283  if ((time - pie->last_measurement) >= pie_cfg->dp_update_interval)
284  _calc_drop_probability(pie_cfg, pie, time);
285 
286  /* Decide whether packet to be dropped or enqueued */
287  if (_rte_pie_drop(pie_cfg, pie) && pie->burst_allowance == 0)
288  return 2;
289  }
290 
291  /* When queue occupancy is over a certain threshold, turn on PIE */
292  if ((pie->active == 0) &&
293  (pie->qlen >= (pie_cfg->tailq_th * 0.1))) {
294  pie->active = 1;
295  pie->qdelay_old = 0;
296  pie->drop_prob = 0;
297  pie->in_measurement = 1;
298  pie->departed_bytes_count = 0;
299  pie->avg_dq_time = 0;
300  pie->last_measurement = time;
301  pie->burst_allowance = pie_cfg->max_burst;
302  pie->accu_prob = 0;
303  pie->start_measurement = time;
304  }
305 
306  /* when queue has been idle for a while, turn off PIE and Reset counters */
307  if (pie->active == 1 &&
308  pie->qlen < (pie_cfg->tailq_th * 0.1)) {
309  pie->active = 0;
310  pie->in_measurement = 0;
311  }
312 
313  /* Update PIE qlen parameter */
314  pie->qlen++;
315  pie->qlen_bytes += pkt_len;
316 
317  /* No drop */
318  return 0;
319 }
320 
335 static inline int
336 __rte_experimental
337 rte_pie_enqueue(const struct rte_pie_config *pie_cfg,
338  struct rte_pie *pie,
339  const unsigned int qlen,
340  uint32_t pkt_len,
341  const uint64_t time)
342 {
343  RTE_ASSERT(pie_cfg != NULL);
344  RTE_ASSERT(pie != NULL);
345 
346  if (qlen != 0)
347  return rte_pie_enqueue_nonempty(pie_cfg, pie, pkt_len, time);
348  else
349  return rte_pie_enqueue_empty(pie_cfg, pie, pkt_len);
350 }
351 
360 static inline void
361 __rte_experimental
362 rte_pie_dequeue(struct rte_pie *pie,
363  uint32_t pkt_len,
364  uint64_t time)
365 {
366  /* Dequeue rate estimation */
367  if (pie->in_measurement) {
368  pie->departed_bytes_count += pkt_len;
369 
370  /* Start a new measurement cycle when enough packets */
372  uint64_t dq_time = time - pie->start_measurement;
373 
374  if (pie->avg_dq_time == 0)
375  pie->avg_dq_time = dq_time;
376  else
377  pie->avg_dq_time = dq_time * RTE_DQ_WEIGHT + pie->avg_dq_time
378  * (1 - RTE_DQ_WEIGHT);
379 
380  pie->in_measurement = 0;
381  }
382  }
383 
384  /* Start measurement cycle when enough data in the queue */
385  if ((pie->qlen_bytes >= RTE_DQ_THRESHOLD) && (pie->in_measurement == 0)) {
386  pie->in_measurement = 1;
387  pie->start_measurement = time;
388  pie->departed_bytes_count = 0;
389  }
390 }
391 
392 #ifdef __cplusplus
393 }
394 #endif
395 
396 #endif /* __RTE_PIE_H_INCLUDED__ */
uint64_t rte_rand(void)
uint64_t start_measurement
Definition: rte_pie.h:63
uint64_t qdelay_ref
Definition: rte_pie.h:50
uint32_t burst_allowance
Definition: rte_pie.h:68
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:155
uint16_t tailq_th
Definition: rte_pie.h:53
#define RTE_DQ_WEIGHT
Definition: rte_pie.h:28
uint64_t qdelay_old
Definition: rte_pie.h:69
#define RTE_RAND_MAX
Definition: rte_pie.h:31
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:364
uint64_t qlen_bytes
Definition: rte_pie.h:66
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:123
double drop_prob
Definition: rte_pie.h:70
#define RTE_DQ_THRESHOLD
Definition: rte_pie.h:23
uint16_t in_measurement
Definition: rte_pie.h:61
double accu_prob
Definition: rte_pie.h:71
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:271
uint32_t departed_bytes_count
Definition: rte_pie.h:62
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:219
#define RTE_BETA
Definition: rte_pie.h:30
uint64_t dp_update_interval
Definition: rte_pie.h:51
uint64_t max_burst
Definition: rte_pie.h:52
uint16_t active
Definition: rte_pie.h:60
uint64_t avg_dq_time
Definition: rte_pie.h:67
#define RTE_ALPHA
Definition: rte_pie.h:29
uint64_t last_measurement
Definition: rte_pie.h:64
uint64_t qlen
Definition: rte_pie.h:65
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:339