[Codel] Fwd: count and rec_inv_sqrt initialization

[Eric Dumazet]

On Fri, 2012-07-06 at 11:20 -0700, Anton Mich wrote:
> I'm looking into the Codel implementation in Linux and the ns-2 and
> ns-3 simulation and found some inconsistency regarding the behavior of
> the count variable.
> 
> Specifically, in the ACM paper the count is decreased by 2 in the
> pseudocode (and ns-3 code) when re-entering a dropping state, in Linux
> the count is reduced to the difference of the current count minus the
> last count, and in ns-2 the count is reduced by 1. I assume that the
> most up to date version is that in linux but for me it's not very
> obvious why we set the value of the count like that, departing from
> the ACM paper intuition.
> 
> Also, when testing the Linux codel scheme I discovered the following
> behavior:
> Because rec_inv_sqrt is initialized to 0, it remains 0 under some
> specific traffic patterns and that forces the interval/rec_inv_sqrt to
> a very small number, no matter what the actual count is. For this not
> to happen we have to enter the else statement that sets: 
> 		
> 		 else {
> 			vars->count = 1;
> 			vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> 			}
> 
> I found that this behavior is fixed when initializing rec_inv_sqrt
> like (reason being that when the newton step is first evaluated, the
> count is equal to 1, so we need a good guess of the rec_inv_sqrt):
> 
> @@ -166,6 +166,7 @@
> static void codel_vars_init(struct codel_vars *vars)
> {
> 	memset(vars, 0, sizeof(*vars));
> +	vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
> }
> 
> Has anybody encountered this behavior? Is this the correct fix?


Hi Anton

Sorry for the delay !

I did some testings and yes, it seems we have an init problem.

But as codel_vars_init() is more often used, I prefer the following
fix :

diff --git a/include/net/codel.h b/include/net/codel.h
index 550debf..c6d92fd 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -305,6 +305,8 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 			}
 		}
 	} else if (drop) {
+		u32 delta;
+
 		if (params->ecn && INET_ECN_set_ce(skb)) {
 			stats->ecn_mark++;
 		} else {
@@ -320,9 +322,10 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 		 * assume that the drop rate that controlled the queue on the
 		 * last cycle is a good starting point to control it now.
 		 */
-		if (codel_time_before(now - vars->drop_next,
-				      16 * params->interval)) {
-			vars->count = (vars->count - vars->lastcount) | 1;
+		delta = vars->count - vars->lastcount;
+		if (delta && codel_time_before(now - vars->drop_next,
+					       16 * params->interval)) {
+			vars->count = delta;
 			/* we dont care if rec_inv_sqrt approximation
 			 * is not very precise :
 			 * Next Newton steps will correct it quadratically.