pie: minor improvements
Subsystems (3)
v2 cover pie: minor improvements
This patch series includes the following minor changes with respect to the PIE/FQ-PIE qdiscs:
- Patch 1 removes some ambiguity by using the term "backlog" instead of "qlen" when referring to the queue length in bytes.
- Patch 2 removes redundant type casting on two expressions.
- Patch 3 removes the pie_vars->accu_prob_overflows variable without affecting the precision in calculations and makes the size of the pie_vars structure exactly 64 bytes.
- Patch 4 realigns a comment affected by a change in patch 3.
Changes from v1 to v2:
- Kept 8 as the argument to prandom_bytes() instead of changing it to 7 as suggested by David Miller.
Leslie Monis (4):
pie: use term backlog instead of qlen
pie: remove unnecessary type casting
pie: remove pie_vars->accu_prob_overflows
pie: realign comment
include/net/pie.h | 31 +++++++++++++--------------- net/sched/sch_fq_pie.c | 1 - net/sched/sch_pie.c | 47 +++++++++++++++++------------------------- 3 files changed, 33 insertions(+), 46 deletions(-)
Signature · 1 line
2.17.1
PATCH v2 1/4 pie: use term backlog instead of qlen
Remove ambiguity by using the term backlog instead of qlen when representing the queue length in bytes.
--- include/net/pie.h | 10 +++++----- net/sched/sch_pie.c | 22 +++++++++++----------- 2 files changed, 16 insertions(+), 16 deletions(-)
include/net/pie.h +5 -5
@@ -46,7 +46,7 @@ struct pie_params {* @accu_prob: accumulated drop probability * @dq_count: number of bytes dequeued in a measurement cycle * @avg_dq_rate: calculated average dq rate -* @qlen_old: queue length during previous qdelay calculation +* @backlog_old: queue backlog during previous qdelay calculation * @accu_prob_overflows: number of times accu_prob overflows */ struct pie_vars {
@@ -58,7 +58,7 @@ struct pie_vars {u64 accu_prob;u64 dq_count;u32 avg_dq_rate; -u32 qlen_old; +u32 backlog_old;u8 accu_prob_overflows; };
@@ -127,12 +127,12 @@ static inline void pie_set_enqueue_time(struct sk_buff *skb) }bool pie_drop_early (struct Qdisc *sch,struct pie_params *params, -struct pie_vars *vars,u32 qlen,u32 packet_size); +struct pie_vars *vars,u32 backlog,u32 packet_size);void pie_process_dequeue (struct sk_buff *skb,struct pie_params *params, -struct pie_vars *vars,u32 qlen); +struct pie_vars *vars,u32 backlog);void pie_calculate_probability (struct pie_params *params,struct pie_vars *vars, -u32 qlen); +u32 backlog);#endif
net/sched/sch_pie.c +11 -11
@@ -31,7 +31,7 @@ struct pie_sched_data { };bool pie_drop_early (struct Qdisc *sch,struct pie_params *params, -struct pie_vars *vars,u32 qlen,u32 packet_size) +struct pie_vars *vars,u32 backlog,u32 packet_size) {u64 rnd;u64 local_prob = vars->prob;
@@ -51,7 +51,7 @@ bool pie_drop_early(struct Qdisc *sch, struct pie_params *params,/* If we have fewer than 2 mtu-sized packets, disable pie_drop_early, * similar to min_th in RED */ -if (qlen <2 * mtu) +if (backlog <2 * mtu)return false;/* If bytemode is turned on, use packet size to compute new
@@ -215,7 +215,7 @@ static int pie_change(struct Qdisc *sch, struct nlattr *opt, }void pie_process_dequeue (struct sk_buff *skb,struct pie_params *params, -struct pie_vars *vars,u32 qlen) +struct pie_vars *vars,u32 backlog) {psched_time_t now =psched_get_time ();u32 dtime =0 ;
@@ -231,7 +231,7 @@ void pie_process_dequeue(struct sk_buff *skb, struct pie_params *params, vars->dq_tstamp = now; -if (qlen ==0 ) +if (backlog ==0 ) vars->qdelay =0 ;if (dtime ==0 )
@@ -244,7 +244,7 @@ void pie_process_dequeue(struct sk_buff *skb, struct pie_params *params,* we have enough packets to calculate the drain rate. Save * current time as dq_tstamp and start measurement cycle. */ -if (qlen >=QUEUE_THRESHOLD && vars->dq_count ==DQCOUNT_INVALID ) { +if (backlog >=QUEUE_THRESHOLD && vars->dq_count ==DQCOUNT_INVALID ) { vars->dq_tstamp =psched_get_time (); vars->dq_count =0 ; }
@@ -283,7 +283,7 @@ void pie_process_dequeue(struct sk_buff *skb, struct pie_params *params,* dq_count to 0 to re-enter the if block when the next * packet is dequeued */ -if (qlen <QUEUE_THRESHOLD ) { +if (backlog <QUEUE_THRESHOLD ) { vars->dq_count =DQCOUNT_INVALID ; }else { vars->dq_count =0 ;
@@ -307,7 +307,7 @@ void pie_process_dequeue(struct sk_buff *skb, struct pie_params *params,EXPORT_SYMBOL_GPL (pie_process_dequeue);void pie_calculate_probability (struct pie_params *params,struct pie_vars *vars, -u32 qlen) +u32 backlog) {psched_time_t qdelay =0 ;/* in pschedtime */ psched_time_t qdelay_old =0 ;/* in pschedtime */
@@ -322,7 +322,7 @@ void pie_calculate_probability(struct pie_params *params, struct pie_vars *vars, vars->qdelay_old = vars->qdelay;if (vars->avg_dq_rate >0 ) - qdelay = (qlen <<PIE_SCALE ) / vars->avg_dq_rate; + qdelay = (backlog <<PIE_SCALE ) / vars->avg_dq_rate;else qdelay =0 ; }else {
@@ -330,10 +330,10 @@ void pie_calculate_probability(struct pie_params *params, struct pie_vars *vars, qdelay_old = vars->qdelay_old; } -/* If qdelay is zero and qlen is not, it means qlen is very small, +/* If qdelay is zero and backlog is not, it means backlog is very small, * so we do not update probabilty in this round. */ -if (qdelay ==0 && qlen !=0 ) +if (qdelay ==0 && backlog !=0 ) update_prob = false;/* In the algorithm, alpha and beta are between 0 and 2 with typical
@@ -409,7 +409,7 @@ void pie_calculate_probability(struct pie_params *params, struct pie_vars *vars, vars->prob -= vars->prob /64 ; vars->qdelay = qdelay; - vars->qlen_old = qlen; + vars->backlog_old = backlog;/* We restart the measurement cycle if the following conditions are met * 1. If the delay has been low for 2 consecutive Tupdate periods
Signature · 1 line
2.17.1
PATCH v2 2/4 pie: remove unnecessary type casting
In reply to Leslie MonisIn function pie_calculate_probability(), the variables alpha and beta are of type u64. The variables qdelay, qdelay_old and params->target are of type psched_time_t (which is also u64). The explicit type casting done when calculating the value for the variable delta is redundant and not required.
--- net/sched/sch_pie.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
net/sched/sch_pie.c +2 -2
@@ -363,8 +363,8 @@ void pie_calculate_probability(struct pie_params *params, struct pie_vars *vars, }/* alpha and beta should be between 0 and 32, in multiples of 1/16 */ - delta += alpha * (u64)(qdelay - params->target); - delta += beta * (u64)(qdelay - qdelay_old); + delta += alpha * (qdelay - params->target); + delta += beta * (qdelay - qdelay_old); oldprob = vars->prob;
Signature · 1 line
2.17.1
PATCH v2 3/4 pie: remove pie_vars->accu_prob_overflows
In reply to Leslie MonisThe variable pie_vars->accu_prob is used as an accumulator for probability values. Since probabilty values are scaled using the MAX_PROB macro denoting (2^64 - 1), pie_vars->accu_prob is likely to overflow as it is of type u64.
The variable pie_vars->accu_prob_overflows counts the number of times the variable pie_vars->accu_prob overflows.
The MAX_PROB macro needs to be equal to at least (2^39 - 1) in order to do precise calculations without any underflow. Thus MAX_PROB can be reduced to (2^56 - 1) without affecting the precision in calculations drastically. Doing so will eliminate the need for the variable pie_vars->accu_prob_overflows as the variable pie_vars->accu_prob will never overflow.
Removing the variable pie_vars->accu_prob_overflows also reduces the size of the structure pie_vars to exactly 64 bytes.
--- include/net/pie.h | 5 +---- net/sched/sch_fq_pie.c | 1 - net/sched/sch_pie.c | 21 ++++++--------------- 3 files changed, 7 insertions(+), 20 deletions(-)
include/net/pie.h +1 -4
@@ -8,7 +8,7 @@#include <net/inet_ecn.h> #include <net/pkt_sched.h> -#define MAX_PROB U64_MAX +#define MAX_PROB (U64_MAX >> BITS_PER_BYTE)#define DTIME_INVALID U64_MAX#define QUEUE_THRESHOLD 16384#define DQCOUNT_INVALID -1
@@ -47,7 +47,6 @@ struct pie_params {* @dq_count: number of bytes dequeued in a measurement cycle * @avg_dq_rate: calculated average dq rate * @backlog_old: queue backlog during previous qdelay calculation -* @accu_prob_overflows: number of times accu_prob overflows */ struct pie_vars {psched_time_t qdelay;
@@ -59,7 +58,6 @@ struct pie_vars {u64 dq_count;u32 avg_dq_rate;u32 backlog_old; -u8 accu_prob_overflows; };/**
@@ -107,7 +105,6 @@ static inline void pie_vars_init(struct pie_vars *vars) vars->accu_prob =0 ; vars->dq_count =DQCOUNT_INVALID ; vars->avg_dq_rate =0 ; - vars->accu_prob_overflows =0 ; }static inline struct pie_skb_cb *get_pie_cb (const struct sk_buff *skb)
net/sched/sch_fq_pie.c +0 -1
@@ -189,7 +189,6 @@ static int fq_pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch, out: q->stats.dropped++; sel_flow->vars.accu_prob =0 ; - sel_flow->vars.accu_prob_overflows =0 ;__qdisc_drop (skb, to_free);qdisc_qstats_drop (sch);return NET_XMIT_CN ;
net/sched/sch_pie.c +6 -15
@@ -62,27 +62,19 @@ bool pie_drop_early(struct Qdisc *sch, struct pie_params *params,else local_prob = vars->prob; -if (local_prob ==0 ) { +if (local_prob ==0 ) vars->accu_prob =0 ; - vars->accu_prob_overflows =0 ; - } - -if (local_prob >MAX_PROB - vars->accu_prob) - vars->accu_prob_overflows++; - - vars->accu_prob += local_prob; +else + vars->accu_prob += local_prob; -if (vars->accu_prob_overflows ==0 && - vars->accu_prob < (MAX_PROB /100 ) *85 ) +if (vars->accu_prob < (MAX_PROB /100 ) *85 )return false; -if (vars->accu_prob_overflows ==8 && - vars->accu_prob >=MAX_PROB /2 ) +if (vars->accu_prob >= (MAX_PROB /2 ) *17 )return true;prandom_bytes (&rnd,8 ); -if (rnd < local_prob) { +if ((rnd >>BITS_PER_BYTE ) < local_prob) { vars->accu_prob =0 ; - vars->accu_prob_overflows =0 ;return true; }
@@ -129,7 +121,6 @@ static int pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch, out: q->stats.dropped++; q->vars.accu_prob =0 ; - q->vars.accu_prob_overflows =0 ;return qdisc_drop (skb, sch, to_free); }
Signature · 1 line
2.17.1
PATCH v2 4/4 pie: realign comment
In reply to Leslie MonisRealign a comment after the change introduced by the previous patch.
--- include/net/pie.h | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-)
include/net/pie.h +9 -9
@@ -38,15 +38,15 @@ struct pie_params {/** * struct pie_vars - contains pie variables -* @qdelay: current queue delay -* @qdelay_old: queue delay in previous qdelay calculation -* @burst_time: burst time allowance -* @dq_tstamp: timestamp at which dq rate was last calculated -* @prob: drop probability -* @accu_prob: accumulated drop probability -* @dq_count: number of bytes dequeued in a measurement cycle -* @avg_dq_rate: calculated average dq rate -* @backlog_old: queue backlog during previous qdelay calculation +* @qdelay: current queue delay +* @qdelay_old: queue delay in previous qdelay calculation +* @burst_time: burst time allowance +* @dq_tstamp: timestamp at which dq rate was last calculated +* @prob: drop probability +* @accu_prob: accumulated drop probability +* @dq_count: number of bytes dequeued in a measurement cycle +* @avg_dq_rate: calculated average dq rate +* @backlog_old: queue backlog during previous qdelay calculation */ struct pie_vars {psched_time_t qdelay;
Signature · 1 line
2.17.1
Quoted 13 lines · On Thu, 5 Mar 2020 00:25:58 +0530 Leslie Monis wrote:
This patch series includes the following minor changes with respect to the PIE/FQ-PIE qdiscs:
- Patch 1 removes some ambiguity by using the term "backlog" instead of "qlen" when referring to the queue length in bytes.
- Patch 2 removes redundant type casting on two expressions.
- Patch 3 removes thepie_vars->accu_prob_overflowsvariable without affecting the precision in calculations and makes the size of thepie_varsstructure exactly 64 bytes.
- Patch 4 realigns a comment affected by a change in patch 3.
Quoted 3 lines
Changes from v1 to v2:
- Kept 8 as the argument toprandom_bytes()instead of changing it to 7 as suggested by David Miller.
I was wondering if patch 3 changes make user-visible changes but it seems those should be only slight accuracy adjustments, so LGTM. FWIW:
David Miller
maintainerFrom: Jakub Kicinski <[email protected]>
Date: Wed, 4 Mar 2020 12:49:17 -0800
Quoted 14 lines · On Thu, 5 Mar 2020 00:25:58 +0530 Leslie Monis wrote:
Quoted 13 lines
This patch series includes the following minor changes with respect to the PIE/FQ-PIE qdiscs:
- Patch 1 removes some ambiguity by using the term "backlog" instead of "qlen" when referring to the queue length in bytes.
- Patch 2 removes redundant type casting on two expressions.
- Patch 3 removes thepie_vars->accu_prob_overflowsvariable without affecting the precision in calculations and makes the size of thepie_varsstructure exactly 64 bytes.
- Patch 4 realigns a comment affected by a change in patch 3.
Quoted 8 lines
Quoted 3 lines
Changes from v1 to v2:
- Kept 8 as the argument toprandom_bytes()instead of changing it to 7 as suggested by David Miller.I was wondering if patch 3 changes make user-visible changes but it seems those should be only slight accuracy adjustments, so LGTM. FWIW:
Reviewed-by Jakub Kicinski <[email protected]>
Series applied, thanks everyone.