[PATCH 4/4] DCCP: Recalculate t_nom on change of t_ipi

[PATCH 4/4] DCCP: Recalculate t_nom on change of t_ipi

[Ian McDonald]

When we recalculate t_nom and t_ipi we should check that t_nom is not
before the current time. If it is then we should set t_nom to current time.

Found this by observing flood of packets when t_ipi decreases.

Also uninline the function as it is big and gcc should decide when to
inline anyway.

Modified this from last iteration by only recalculate if t_ipi drops to
save expensive operations on time.

Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
---
diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
index e93bae5..ea22d08 100644
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -84,8 +84,12 @@ static void ccid3_hc_tx_set_state(struct sock *sk,
  * Recalculate scheduled nominal send time t_nom, inter-packet interval
  * t_ipi, and delta value. Should be called after each change to X.
  */
-static inline void ccid3_update_send_time(struct ccid3_hc_tx_sock *hctx)
+static void ccid3_update_send_time(struct sock *sk)
 {
+	struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
+	suseconds_t delay;
+	u32 old_t_ipi = hctx->ccid3hctx_t_ipi;
+
 	timeval_sub_usecs(&hctx->ccid3hctx_t_nom, hctx->ccid3hctx_t_ipi);
 
 	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
@@ -103,6 +107,18 @@ static inline void ccid3_update_send_time(struct ccid3_hc_tx_sock *hctx)
 	               hctx->ccid3hctx_t_ipi, hctx->ccid3hctx_delta,
 		       hctx->ccid3hctx_s, hctx->ccid3hctx_x >> 6);
 
+	if (old_t_ipi > hctx->ccid3hctx_t_ipi) {
+		struct timeval now;
+		dccp_timestamp(sk, &now);
+
+		/* we want to check if before current time so we don't send a
+		 * flood of packets */
+		delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
+		if (delay < 0) {
+			hctx->ccid3hctx_t_nom = now;
+			ccid3_pr_debug("reset t_nom\n");
+		}
+	}
 }
 /*
  * Update X by
@@ -149,7 +165,7 @@ static void ccid3_hc_tx_update_x(struct sock *sk, struct timeval *now)
 		ccid3_pr_debug("X_prev=%llu, X_now=%llu, X_calc=%u, "
 		               "X_recv=%llu\n", old_x, hctx->ccid3hctx_x,
 			       hctx->ccid3hctx_x_calc, hctx->ccid3hctx_x_recv);
-		ccid3_update_send_time(hctx);
+		ccid3_update_send_time(sk);
 	}
 }
 
@@ -226,7 +242,7 @@ static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
 		/* The value of R is still undefined and so we can not recompute
 		 * the timout value. Keep initial value as per [RFC 4342, 5]. */
 		t_nfb = TFRC_INITIAL_TIMEOUT;
-		ccid3_update_send_time(hctx);
+		ccid3_update_send_time(sk);
 		break;
 	case TFRC_SSTATE_FBACK:
 		/*
@@ -485,7 +501,7 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
 			hctx->ccid3hctx_x    = scaled_div(w_init << 6, r_sample);
 			hctx->ccid3hctx_t_ld = now;
 
-			ccid3_update_send_time(hctx);
+			ccid3_update_send_time(sk);
 
 			ccid3_pr_debug("%s(%p), s=%u, MSS=%u, w_init=%u, "
 				       "R_sample=%dus, X=%u\n", dccp_role(sk),

Re: [PATCH 4/4] DCCP: Recalculate t_nom on change of t_ipi

[Gerrit Renker]

Ian is right that there is a problem, but this fixes one symptom, but there are
two causes, which are not resolved by this patch:

 (1) t_nom becoming negative is caused by tardiness in packet scheduling
     and therefore it should be resolved at the location which deals with packet
     sending (ccid3_hc_tx_send_packet), and not in ccid3_update_send_time()

 (2) Using this routine carries with it a race condition: several functions
     (ccid3_hc_tx_send_packet, this routine, ccid3_hc_tx_update_x, ccid3_hc_tx_packet_recv)
     have asynchronous, concurrent read-write access to t_nom. 

Please see earlier discussion on `tardiness bug' and the detailed analysis provided with
the `race condition' patch.

Gerrit

Quoting Ian McDonald:
|  diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
|  index e93bae5..ea22d08 100644
|  --- a/net/dccp/ccids/ccid3.c
|  +++ b/net/dccp/ccids/ccid3.c
|  @@ -84,8 +84,12 @@ static void ccid3_hc_tx_set_state(struct sock *sk,
|    * Recalculate scheduled nominal send time t_nom, inter-packet interval
|    * t_ipi, and delta value. Should be called after each change to X.
|    */
|  -static inline void ccid3_update_send_time(struct ccid3_hc_tx_sock *hctx)
|  +static void ccid3_update_send_time(struct sock *sk)
|   {
|  +	struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
|  +	suseconds_t delay;
|  +	u32 old_t_ipi = hctx->ccid3hctx_t_ipi;
|  +
|   	timeval_sub_usecs(&hctx->ccid3hctx_t_nom, hctx->ccid3hctx_t_ipi);
|   
|   	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
|  @@ -103,6 +107,18 @@ static inline void ccid3_update_send_time(struct ccid3_hc_tx_sock *hctx)
|   	               hctx->ccid3hctx_t_ipi, hctx->ccid3hctx_delta,
|   		       hctx->ccid3hctx_s, hctx->ccid3hctx_x >> 6);
|   
|  +	if (old_t_ipi > hctx->ccid3hctx_t_ipi) {
|  +		struct timeval now;
|  +		dccp_timestamp(sk, &now);
|  +
|  +		/* we want to check if before current time so we don't send a
|  +		 * flood of packets */
|  +		delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
|  +		if (delay < 0) {
|  +			hctx->ccid3hctx_t_nom = now;
|  +			ccid3_pr_debug("reset t_nom\n");
|  +		}
|  +	}
|   }
|   /*
|    * Update X by
|  @@ -149,7 +165,7 @@ static void ccid3_hc_tx_update_x(struct sock *sk, struct timeval *now)
|   		ccid3_pr_debug("X_prev=%llu, X_now=%llu, X_calc=%u, "
|   		               "X_recv=%llu\n", old_x, hctx->ccid3hctx_x,
|   			       hctx->ccid3hctx_x_calc, hctx->ccid3hctx_x_recv);
|  -		ccid3_update_send_time(hctx);
|  +		ccid3_update_send_time(sk);
|   	}
|   }
|   
|  @@ -226,7 +242,7 @@ static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
|   		/* The value of R is still undefined and so we can not recompute
|   		 * the timout value. Keep initial value as per [RFC 4342, 5]. */
|   		t_nfb = TFRC_INITIAL_TIMEOUT;
|  -		ccid3_update_send_time(hctx);
|  +		ccid3_update_send_time(sk);
|   		break;
|   	case TFRC_SSTATE_FBACK:
|   		/*
|  @@ -485,7 +501,7 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
|   			hctx->ccid3hctx_x    = scaled_div(w_init << 6, r_sample);
|   			hctx->ccid3hctx_t_ld = now;
|   
|  -			ccid3_update_send_time(hctx);
|  +			ccid3_update_send_time(sk);
|   
|   			ccid3_pr_debug("%s(%p), s=%u, MSS=%u, w_init=%u, "
|   				       "R_sample=%dus, X=%u\n", dccp_role(sk),
|  -
|  To unsubscribe from this list: send the line "unsubscribe dccp" in
|  the body of a message to majordomo@vger.kernel.org
|  More majordomo info at  http://vger.kernel.org/majordomo-info.html
|  
|  

Re: [PATCH 4/4] DCCP: Recalculate t_nom on change of t_ipi

[Ian McDonald]

On 1/4/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> Ian is right that there is a problem, but this fixes one symptom, but there are
> two causes, which are not resolved by this patch:
>
>  (1) t_nom becoming negative is caused by tardiness in packet scheduling
>      and therefore it should be resolved at the location which deals with packet
>      sending (ccid3_hc_tx_send_packet), and not in ccid3_update_send_time()
>
I thought my solution was better. I originally implemented the same
solution as you and then realised this point 1 you discuss. But it
should be negative in these cases as per RFC 3448 4.6

When a sender first starts sending at time t_0, it calculates t_ipi,
   and calculates a nominal send time t_1 = t_0 + t_ipi for packet 1.
   When the application becomes idle, it checks the current time, t_now,
   and then requests re-scheduling after (t_ipi - (t_now - t_0))
   seconds.  When the application is re-scheduled, it checks the current
   time, t_now, again.  If (t_now > t_1 - delta) then packet 1 is sent.

   Now a new t_ipi may be calculated, and used to calculate a nominal
   send time t_2 for packet 2: t2 = t_1 + t_ipi.  The process then
   repeats, with each successive packet's send time being calculated
   from the nominal send time of the previous packet.

   In some cases, when the nominal send time, t_i, of the next packet is
   calculated, it may already be the case that t_now > t_i - delta.  In
   such a case the packet should be sent immediately.  Thus if the
   operating system has coarse timer granularity and the transmit rate

   is high, then TFRC may send short bursts of several packets separated
   by intervals of the OS timer granularity.

Note there that several packets can be sent in bursts. Your code stops
this and slows transmit down quite a lot.

However I think now my solution is not perfect. What I was trying to
work around and fix was that the t_ipi gets altered down from 1
second.

However thinking about it some more we are doing this the wrong way
altogether and should do it in the sending loop ONLY as per the
suggestion (not requirement) at the top of section 4.6

   As TFRC is rate-based, and as operating systems typically cannot
   schedule events precisely, it is necessary to be opportunistic about
   sending data packets so that the correct average rate is maintained
   despite the course-grain or irregular scheduling of the operating
   system.  Thus a typical sending loop will calculate the correct
   inter-packet interval, t_ipi, as follows:

        t_ipi = s/X_inst;

The special case that we need to deal with is this one from section 5
of RFC4342:
   [RFC3448], Section 4, specifies an initial sending rate of one packet
   per round-trip time (RTT) as follows: The sender initializes the
   allowed sending rate to one packet per second.  As soon as a feedback
   packet is received from the receiver, the sender has a measurement of
   the round-trip time and then sets the initial allowed sending rate to
   one packet per RTT.

>  (2) Using this routine carries with it a race condition: several functions
>      (ccid3_hc_tx_send_packet, this routine, ccid3_hc_tx_update_x, ccid3_hc_tx_packet_recv)
>      have asynchronous, concurrent read-write access to t_nom.
>
> Please see earlier discussion on `tardiness bug' and the detailed analysis provided with
> the `race condition' patch.
>
I think that rewriting this code as per point 1 will eliminate this
problem provided we do it properly.

So the short answer is we both made improvements but we've both got it
not quite right and we need to revise again.

Ian
-- 
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group

Re: [PATCH 4/4] DCCP: Recalculate t_nom on change of t_ipi

[Gerrit Renker]

|  > there are two causes, which are not resolved by this patch:
|  >
|  >  (1) t_nom becoming negative is caused by tardiness in packet scheduling
|  >      and therefore it should be resolved at the location which deals with packet
|  >      sending (ccid3_hc_tx_send_packet), and not in ccid3_update_send_time()
|  >
|  I thought my solution was better. I originally implemented the same
|  solution as you and then realised this point 1 you discuss. But it
|  should be negative in these cases as per RFC 3448 4.6
|  
|  When a sender first starts sending at time t_0, it calculates t_ipi,
We have had this discussion in detail before, please see
http://www.mail-archive.com/dccp@vger.kernel.org/msg00841.html

  
|  Note there that several packets can be sent in bursts. Your code stops
|  this and slows transmit down quite a lot.
Under which conditions are packets sent in bursts? 

RFC 3448, 4.6 considers coarse timer granularity. However, the problem considered here
is when a packet is scheduled for sending after it was due - tardiness. 

You are saying that my "code stops this and slows transmit down quite a lot". 
This is not true:
 * when tardiness does not occur and packet scheduling is always within bounds, 
   the issue does not arise - we are doing as the RFC says.
 * when tardiness occurs then it is a problem of the packet scheduling engine, but
   not of the calculation of t_ipi. 
In simple terms, tardiness is either a bug (when occurs constantly) or it is an overload
indicator. What my patch does is avoid further damage when such a condition occurs and there
is no doubt here that it should.
What you are proposing above is that reacting to an error condition stops sending a burst of
packets and that therefore it "slows transmit down quite a lot". 
I am not convinced since your argumentation is only valid if the bug/overload case occurs. My
suggestion is to add a warning message when tardiness occurs, but not try to fix a possible
bug/overload condition by changing the way t_ipi is calculated.

|  
|  However I think now my solution is not perfect. What I was trying to
|  work around and fix was that the t_ipi gets altered down from 1
|  second.
Sorry I don't get the reason for this. 
  
|  However thinking about it some more we are doing this the wrong way
|  altogether and should do it in the sending loop ONLY as per the
|  suggestion (not requirement) at the top of section 4.6
Please have a look at the other patch which fixes the race condition; indeed it
makes sure that t_nom is only updated in the sending loop. With regard to t_ipi, 
it is best to update it as soon as new data becomes available.

  
|  The special case that we need to deal with is this one from section 5
|  of RFC4342:
|     [RFC3448], Section 4, specifies an initial sending rate of one packet
|     per round-trip time (RTT) as follows: The sender initializes the
|     allowed sending rate to one packet per second.  As soon as a feedback
|     packet is received from the receiver, the sender has a measurement of
|     the round-trip time and then sets the initial allowed sending rate to
|     one packet per RTT.
This has been done already - support for larger initial windows in hc_tx_packet_recv.


|  
|  >  (2) Using this routine carries with it a race condition: several functions
|  >      (ccid3_hc_tx_send_packet, this routine, ccid3_hc_tx_update_x, ccid3_hc_tx_packet_recv)
|  >      have asynchronous, concurrent read-write access to t_nom.
|  >
|  > Please see earlier discussion on `tardiness bug' and the detailed analysis provided with
|  > the `race condition' patch.
|  >
|  I think that rewriting this code as per point 1 will eliminate this
|  problem provided we do it properly.
|  
|  So the short answer is we both made improvements but we've both got it
|  not quite right and we need to revise again.
I remain to be convinced where we "got it not quite right": we need to catch the bug/overload
condition and we must ensure that race conditions are avoided. Both are taken care of by the
patches I sent. 

Sorry I fail to see what problem you are trying to fix. Of course, it is regrettable when bursts
of packets can not be sent due to tardiness. But, as already explained above, this condition only
appears when there is either (i) a bug in the scheduling engine or (ii) an overload condition.

While I think that (i) is unlikely; if it occurs then we need to reconsider the packet scheduling
(dccp_wait_for_ccid, dccp_write_xmit_timer and related functions), but not the code to calculate
t_nom and t_ipi.

In case (ii) sending bursts of packets is not possible anyhow, since the OS/NIC/network first needs
to recover from the overload condition.

Hence the only point where I agree with you is to add a warning message whenever the tardiness condition
occurs in hc_tx_send_packet, to see whether (i) holds. I am NOT in support of code to deal with (ii).