--- name: "rte_red_mark_queue_empty" section: "3" platform: "linux" package: "dpdk-doc" version: "24.11.4-0+deb13u1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/rte_red.h" --- # rte\_red\_mark\_queue\_empty(3) Part of [rte\_red.h(3)](/rte_red.h/3.md). ## NAME rte\_red.h ## SYNOPSIS `#include `\ `#include `\ `#include `\ `#include `\ `#include `\ ### Data Structures struct **rte\_red\_params**\ struct **rte\_red\_config**\ struct **rte\_red**\ ### Macros \#define **RTE\_RED\_SCALING** 10\ \#define **RTE\_RED\_S** (1 \<\< 22)\ \#define **RTE\_RED\_MAX\_TH\_MAX** 1023\ \#define **RTE\_RED\_WQ\_LOG2\_MIN** 1\ \#define **RTE\_RED\_WQ\_LOG2\_MAX** 12\ \#define **RTE\_RED\_MAXP\_INV\_MIN** 1\ \#define **RTE\_RED\_MAXP\_INV\_MAX** 255\ \#define **RTE\_RED\_2POW16** (1\<\<16)\ ### Functions int **rte\_red\_rt\_data\_init** (struct **rte\_red** \*red)\ Initialises run-time data. int **rte\_red\_config\_init** (struct **rte\_red\_config** \*red\_cfg, const uint16\_t wq\_log2, const uint16\_t min\_th, const uint16\_t max\_th, const uint16\_t maxp\_inv)\ Configures a single RED configuration parameter structure. static uint32\_t **rte\_fast\_rand** (void)\ Generate random number for RED. static uint16\_t **\_\_rte\_red\_calc\_qempty\_factor** (uint8\_t wq\_log2, uint16\_t m)\ calculate factor to scale average queue size when queue becomes empty static int **rte\_red\_enqueue\_empty** (const struct **rte\_red\_config** \*red\_cfg, struct **rte\_red** \*red, const uint64\_t time)\ Updates queue average in condition when queue is empty. static int **\_\_rte\_red\_drop** (const struct **rte\_red\_config** \*red\_cfg, struct **rte\_red** \*red)\ make a decision to drop or enqueue a packet based on mark probability criteria static int **rte\_red\_enqueue\_nonempty** (const struct **rte\_red\_config** \*red\_cfg, struct **rte\_red** \*red, const unsigned q)\ Decides if new packet should be enqueued or dropped in queue non-empty case. static int **rte\_red\_enqueue** (const struct **rte\_red\_config** \*red\_cfg, struct **rte\_red** \*red, const unsigned q, const uint64\_t time)\ Decides if new packet should be enqueued or dropped Updates run time data based on new queue size value. Based on new queue average and RED configuration parameters gives verdict whether to enqueue or drop the packet. static void **rte\_red\_mark\_queue\_empty** (struct **rte\_red** \*red, const uint64\_t time)\ Callback to records time that queue became empty. ### Variables uint32\_t **rte\_red\_rand\_val**\ ## Detailed Description RTE Random Early Detection (RED) Definition in file **rte\_red.h**. ## Macro Definition Documentation ### #define RTE\_RED\_SCALING 10 Fraction size for fixed-point Definition at line **23** of file **rte\_red.h**. ### #define RTE\_RED\_S (1 \<\< 22) Packet size multiplied by number of leaf queues Definition at line **24** of file **rte\_red.h**. ### #define RTE\_RED\_MAX\_TH\_MAX 1023 Max threshold limit in fixed point format Definition at line **25** of file **rte\_red.h**. ### #define RTE\_RED\_WQ\_LOG2\_MIN 1 Min inverse filter weight value Definition at line **26** of file **rte\_red.h**. ### #define RTE\_RED\_WQ\_LOG2\_MAX 12 Max inverse filter weight value Definition at line **27** of file **rte\_red.h**. ### #define RTE\_RED\_MAXP\_INV\_MIN 1 Min inverse mark probability value Definition at line **28** of file **rte\_red.h**. ### #define RTE\_RED\_MAXP\_INV\_MAX 255 Max inverse mark probability value Definition at line **29** of file **rte\_red.h**. ### #define RTE\_RED\_2POW16 (1\<\<16) 2 power 16 Definition at line **30** of file **rte\_red.h**. ## Function Documentation ### int rte\_red\_rt\_data\_init (struct rte\_red \* red) Initialises run-time data. **Parameters** *red* \[in,out\] data pointer to RED runtime data **Returns** Operation status **Return values** *0* success \ *!0* error ### int rte\_red\_config\_init (struct rte\_red\_config \* red\_cfg, const uint16\_t wq\_log2, const uint16\_t min\_th, const uint16\_t max\_th, const uint16\_t maxp\_inv) Configures a single RED configuration parameter structure. **Parameters** *red\_cfg* \[in,out\] config pointer to a RED configuration parameter structure \ *wq\_log2* \[in\] log2 of the filter weight, valid range is: RTE\_RED\_WQ\_LOG2\_MIN \<= wq\_log2 \<= RTE\_RED\_WQ\_LOG2\_MAX \ *min\_th* \[in\] queue minimum threshold in number of packets \ *max\_th* \[in\] queue maximum threshold in number of packets \ *maxp\_inv* \[in\] inverse maximum mark probability **Returns** Operation status **Return values** *0* success \ *!0* error ### static uint32\_t rte\_fast\_rand (void)` [inline]`, ` [static]` Generate random number for RED. Implementation based on: http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/ 10 bit shift has been found through empirical tests (was 16). **Returns** Random number between 0 and (2^22 - 1) Definition at line **116** of file **rte\_red.h**. ### static uint16\_t \_\_rte\_red\_calc\_qempty\_factor (uint8\_t wq\_log2, uint16\_t m)` [inline]`, ` [static]` calculate factor to scale average queue size when queue becomes empty **Parameters** *wq\_log2* \[in\] where EWMA filter weight wq = 1/(2 ^ wq\_log2) \ *m* \[in\] exponent in the computed value (1 - wq) ^ m **Returns** computed value **Return values** *((1* - wq) ^ m) scaled in fixed-point format Basic math tells us that: a^b = 2^(b \* log2(a) ) in our case: a = (1-Wq) b = m Wq = 1/ (2^log2n) So we are computing this equation: factor = 2 ^ ( m \* log2(1-Wq)) First we are computing: n = m \* log2(1-Wq) To avoid dealing with signed numbers log2 values are positive but they should be negative because (1-Wq) is always \< 1. Contents of log2 table values are also scaled for precision. The tricky part is computing 2^n, for this I split n into integer part and fraction part. f - is fraction part of n n - is integer part of original n Now using basic math we compute 2^n: 2^(f+n) = 2^f \* 2^n 2^f - we use lookup table 2^n - can be replaced with bit shift right operations Definition at line **133** of file **rte\_red.h**. ### static int rte\_red\_enqueue\_empty (const struct rte\_red\_config \* red\_cfg, struct rte\_red \* red, const uint64\_t time)` [inline]`, ` [static]` Updates queue average in condition when queue is empty. Note: packet is never dropped in this particular case. **Parameters** *red\_cfg* \[in\] config pointer to a RED configuration parameter structure \ *red* \[in,out\] data pointer to RED runtime data \ *time* \[in\] current time stamp **Returns** Operation status **Return values** *0* enqueue the packet \ *1* drop the packet based on max threshold criterion \ *2* drop the packet based on mark probability criterion We compute avg but we don't compare avg against min\_th or max\_th, nor calculate drop probability m is the number of packets that might have arrived while the queue was empty. In this case we have time stamps provided by scheduler in byte units (bytes transmitted on network port). Such time stamp translates into time units as port speed is fixed but such approach simplifies the code. Check that m will fit into 16-bit unsigned integer Definition at line **196** of file **rte\_red.h**. ### static int \_\_rte\_red\_drop (const struct rte\_red\_config \* red\_cfg, struct rte\_red \* red)` [inline]`, ` [static]` make a decision to drop or enqueue a packet based on mark probability criteria Drop probability (Sally Floyd and Van Jacobson): pb = (1 / maxp\_inv) \* (avg - min\_th) / (max\_th - min\_th) pa = pb / (2 - count \* pb) ``` (1 / maxp_inv) * (avg - min_th) --------------------------------- max_th - min_th ``` pa = ----------------------------------------------- count \* (1 / maxp\_inv) \* (avg - min\_th) 2 - ----------------------------------------- max\_th - min\_th ``` avg - min_th ``` pa = ----------------------------------------------------------- 2 \* (max\_th - min\_th) \* maxp\_inv - count \* (avg - min\_th) We define pa\_const as: pa\_const = 2 \* (max\_th - min\_th) \* maxp\_inv. Then: ``` avg - min_th ``` pa = ----------------------------------- pa\_const - count \* (avg - min\_th) **Parameters** *red\_cfg* \[in\] config pointer to structure defining RED parameters \ *red* \[in,out\] data pointer to RED runtime data **Returns** operation status **Return values** *0* enqueue the packet \ *1* drop the packet Definition at line **274** of file **rte\_red.h**. ### static int rte\_red\_enqueue\_nonempty (const struct rte\_red\_config \* red\_cfg, struct rte\_red \* red, const unsigned q)` [inline]`, ` [static]` Decides if new packet should be enqueued or dropped in queue non-empty case. **Parameters** *red\_cfg* \[in\] config pointer to a RED configuration parameter structure \ *red* \[in,out\] data pointer to RED runtime data \ *q* \[in\] current queue size (measured in packets) **Returns** Operation status **Return values** *0* enqueue the packet \ *1* drop the packet based on max threshold criterion \ *2* drop the packet based on mark probability criterion EWMA filter (Sally Floyd and Van Jacobson): avg = (1 - wq) \* avg + wq \* q avg = avg + q \* wq - avg \* wq We select: wq = 2^(-n). Let scaled version of avg be: avg\_s = avg \* 2^(N+n). We get: avg\_s = avg\_s + q \* 2^N - avg\_s \* 2^(-n) By using shift left/right operations, we get: avg\_s = avg\_s + (q \<\< N) - (avg\_s \>\> n) avg\_s += (q \<\< N) - (avg\_s \>\> n) Definition at line **313** of file **rte\_red.h**. ### static int rte\_red\_enqueue (const struct rte\_red\_config \* red\_cfg, struct rte\_red \* red, const unsigned q, const uint64\_t time)` [inline]`, ` [static]` Decides if new packet should be enqueued or dropped Updates run time data based on new queue size value. Based on new queue average and RED configuration parameters gives verdict whether to enqueue or drop the packet. **Parameters** *red\_cfg* \[in\] config pointer to a RED configuration parameter structure \ *red* \[in,out\] data pointer to RED runtime data \ *q* \[in\] updated queue size in packets \ *time* \[in\] current time stamp **Returns** Operation status **Return values** *0* enqueue the packet \ *1* drop the packet based on max threshold criteria \ *2* drop the packet based on mark probability criteria Definition at line **375** of file **rte\_red.h**. ### static void rte\_red\_mark\_queue\_empty (struct rte\_red \* red, const uint64\_t time)` [inline]`, ` [static]` Callback to records time that queue became empty. **Parameters** *red* \[in,out\] data pointer to RED runtime data \ *time* \[in\] current time stamp Definition at line **397** of file **rte\_red.h**. ## Variable Documentation ### uint32\_t rte\_red\_rand\_val` [extern]` Externs ## Author Generated automatically by Doxygen for DPDK from the source code.