[PATCH 2/3]: Provide 10s of microsecond timesource

[PATCH 2/3]: Provide 10s of microsecond timesource

[Gerrit Renker]

[DCCP]: Provide 10s of microsecond timesource

This provides a timesource, conveniently used for DCCP timestamps, which 
returns the elapsed time in 10s of microseconds since initialisation. 
This makes for a wrap-around time of about 11.9 hours, which should be
sufficient for most applications.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/dccp.h    |    2 ++
 net/dccp/options.c |    2 +-
 net/dccp/proto.c   |    2 ++
 net/dccp/timer.c   |   21 +++++++++++++++++++++
 4 files changed, 26 insertions(+), 1 deletion(-)

--- a/net/dccp/dccp.h
+++ b/net/dccp/dccp.h
@@ -396,6 +396,8 @@ extern int dccp_insert_options(struct so
 extern int dccp_insert_option_elapsed_time(struct sock *sk,
 					    struct sk_buff *skb,
 					    u32 elapsed_time);
+extern u32 dccp_timestamp(void);
+extern void dccp_timestamping_init(void);
 extern int dccp_insert_option_timestamp(struct sock *sk,
 					 struct sk_buff *skb);
 extern int dccp_insert_option(struct sock *sk, struct sk_buff *skb,
--- a/net/dccp/options.c
+++ b/net/dccp/options.c
@@ -372,7 +372,7 @@ EXPORT_SYMBOL_GPL(dccp_insert_option_ela
 
 int dccp_insert_option_timestamp(struct sock *sk, struct sk_buff *skb)
 {
-	__be32 now = htonl(((suseconds_t)ktime_to_us(ktime_get_real())) / 10);
+	__be32 now = htonl(dccp_timestamp());
 	/* yes this will overflow but that is the point as we want a
 	 * 10 usec 32 bit timer which mean it wraps every 11.9 hours */
 
--- a/net/dccp/proto.c
+++ b/net/dccp/proto.c
@@ -1076,6 +1076,8 @@ static int __init dccp_init(void)
 	rc = dccp_sysctl_init();
 	if (rc)
 		goto out_ackvec_exit;
+
+	dccp_timestamping_init();
 out:
 	return rc;
 out_ackvec_exit:
--- a/net/dccp/timer.c
+++ b/net/dccp/timer.c
@@ -291,3 +291,24 @@ void dccp_init_xmit_timers(struct sock *
 	inet_csk_init_xmit_timers(sk, &dccp_write_timer, &dccp_delack_timer,
 				  &dccp_keepalive_timer);
 }
+
+static ktime_t dccp_timestamp_seed;
+/**
+ * dccp_timestamp  -  10s of microseconds time source
+ * Returns the number of hundredths of milliseconds since initialisation. This
+ * is the native DCCP time difference format (RFC 4340, sec. 13); the counter
+ * wraps around circa every 11.9 hours, so careful with marathon TV watching :)
+ */
+u32 dccp_timestamp(void)
+{
+	s64 delta = ktime_us_delta(ktime_get_real(), dccp_timestamp_seed);
+
+	do_div(delta, 10);
+	return delta;
+}
+EXPORT_SYMBOL_GPL(dccp_timestamp);
+
+void __init dccp_timestamping_init(void)
+{
+	dccp_timestamp_seed = ktime_get_real();
+}

Re: [PATCH 2/3]: Provide 10s of microsecond timesource

[Arnaldo Carvalho de Melo]

Em Tue, Aug 21, 2007 at 08:00:16PM +0100, Gerrit Renker escreveu:
> [DCCP]: Provide 10s of microsecond timesource
> 
> This provides a timesource, conveniently used for DCCP timestamps, which 
> returns the elapsed time in 10s of microseconds since initialisation. 
> This makes for a wrap-around time of about 11.9 hours, which should be
> sufficient for most applications.

Why do it at kernel boot (or at dccp module load time to be more
precise)? Why not do it at sock creation time? Then it will be 11.9
hours after the socket is created.

This is how dccps_epoch was used BTW :-)

- Arnaldo

Re: [PATCH 2/3]: Provide 10s of microsecond timesource

[Gerrit Renker]

Quoting Arnaldo Carvalho de Melo:
|  > [DCCP]: Provide 10s of microsecond timesource
|  > 
|  > This provides a timesource, conveniently used for DCCP timestamps, which 
|  > returns the elapsed time in 10s of microseconds since initialisation. 
|  > This makes for a wrap-around time of about 11.9 hours, which should be
|  > sufficient for most applications.
|  
|  Why do it at kernel boot (or at dccp module load time to be more
|  precise)? Why not do it at sock creation time? Then it will be 11.9
|  hours after the socket is created.
|  
|  This is how dccps_epoch was used BTW :-)
This was done intentionally to keep it small. I figured that if there are e.g.
60 sockets, then each of them needs a ktime_t variable, plus an initialisation
(and another one for child sockets); and then it may be that the dccp_timestamp()
is never called: currently the only customer of dccp_timestamp() is CCID3 (for
the SYN RTT sample). If CCID2 is used, then all this is provided but not used.
Hence, for the occasional timestamp keeping it separate comes at a lower cost.

Actually, the problem is not like the sequence number arithmetic, since normal
subtraction (not modulo-2^32 subtraction) is used, i.e. if the socket is created
5 seconds before the 32-bit value wraps around, then 5 seconds later the time
difference to an earlier timestamp would reach a huge value (2^32 - 1 - 5 seconds).

To avoid this problem, one would have to use modulo-2^32 subtraction, ie. cast to
s64 and see if the difference is negative, and add 2^32 if it is.

But this all seems to me over-engineering: the problem occurs only every 11.9 hours,
and if it occurs earlier, it is caught by dccp_sample_rtt() which will reduce the 
huge value to 3 seconds (max RTT).

And it is once again CCID3 which causes these headaches with its dependence on precision.

I can see the following alternatives, what is your stance regarding:
 (a) keep as it is (probably not agreeing due to this email?)
 (b) keep principle, but use at socket creation (glitch comes possibly later, but will still occur)
 (c) ditch principle and use even lower granularity - milliseconds (jiffies seems like a natural match)

My personal favourite is (c).
	

Re: [PATCH 2/3]: Provide 10s of microsecond timesource

[Arnaldo Carvalho de Melo]

Em Wed, Aug 22, 2007 at 09:31:13AM +0100, Gerrit Renker escreveu:
> Quoting Arnaldo Carvalho de Melo:
> |  > [DCCP]: Provide 10s of microsecond timesource
> |  > 
> |  > This provides a timesource, conveniently used for DCCP timestamps, which 
> |  > returns the elapsed time in 10s of microseconds since initialisation. 
> |  > This makes for a wrap-around time of about 11.9 hours, which should be
> |  > sufficient for most applications.
> |  
> |  Why do it at kernel boot (or at dccp module load time to be more
> |  precise)? Why not do it at sock creation time? Then it will be 11.9
> |  hours after the socket is created.
> |  
> |  This is how dccps_epoch was used BTW :-)
> This was done intentionally to keep it small. I figured that if there are e.g.
> 60 sockets, then each of them needs a ktime_t variable, plus an initialisation
> (and another one for child sockets); and then it may be that the dccp_timestamp()
> is never called: currently the only customer of dccp_timestamp() is CCID3 (for
> the SYN RTT sample). If CCID2 is used, then all this is provided but not used.
> Hence, for the occasional timestamp keeping it separate comes at a lower cost.
> 
> Actually, the problem is not like the sequence number arithmetic, since normal
> subtraction (not modulo-2^32 subtraction) is used, i.e. if the socket is created
> 5 seconds before the 32-bit value wraps around, then 5 seconds later the time
> difference to an earlier timestamp would reach a huge value (2^32 - 1 - 5 seconds).
> 
> To avoid this problem, one would have to use modulo-2^32 subtraction, ie. cast to
> s64 and see if the difference is negative, and add 2^32 if it is.
> 
> But this all seems to me over-engineering: the problem occurs only every 11.9 hours,
> and if it occurs earlier, it is caught by dccp_sample_rtt() which will reduce the 
> huge value to 3 seconds (max RTT).
> 
> And it is once again CCID3 which causes these headaches with its dependence on precision.
> 
> I can see the following alternatives, what is your stance regarding:
>  (a) keep as it is (probably not agreeing due to this email?)
>  (b) keep principle, but use at socket creation (glitch comes possibly later, but will still occur)
>  (c) ditch principle and use even lower granularity - milliseconds (jiffies seems like a natural match)
> 
> My personal favourite is (c).

I think that we should provide the best granularity available we can
while not impacting non DCCP code (remember the net_enable_timestamp()
case?). CCID3 probably is what people will try first, I guess.

Well, I'll merge your patches as is, it fixes the bug I introduced and
as you say dccp_sample_rtt will bound it to max RTT.

On the overengineering front I just thought that if this is needed just
by some CCIDs then the initialization costs could be shifted to
ccid_hc_tx_init and the option insertion to ccid_hc_tx_insert_option...
Just checked and dccp_insert_option_timestamp already is called only
from two places: ccid3 and from dccp_insert_options when sending the
REQUEST packet, also on behalf of ccid3, I'll check if we can somehow
shift this option insertion in the REQUEST packet entirely to the
CCID3 code.

Humm, there is also elapsed time in dccp_timestamp_echo, but that is a
delta, so we should have enough space on 32 bits... but because of that
we need to do timestamping on dccp_parse_options and not in the CCID
code that needs this... i.e. if we want to avoid having dccps_epoch in
dccp_sock we might as well get rid of dccps_timestamp_time and
dccps_timestamp_echo, shifting it to some other struct that would be
inserted on any CCID that wants to use these timestamping.

Checking RFC4341 (CCID2):

   6. The sender estimates round-trip times, either through keeping
      track of acknowledgement round-trip times as TCP does or through
      explicit Timestamp options, and calculates a TimeOut (TO) value
      much as the RTO (Retransmit Timeout) is calculated in TCP.  The TO
      determines when a new DCCP-Data packet can be transmitted when the
      sender has been limited by the congestion window and no feedback
      has been received from the receiver.

Nah for now I'll merge your patches as is and do some testing this time around.

- Arnaldo

Re: [PATCH 2/3]: Provide 10s of microsecond timesource

[Gerrit Renker]

|  > I can see the following alternatives, what is your stance regarding:
|  >  (a) keep as it is (probably not agreeing due to this email?)
|  >  (b) keep principle, but use at socket creation (glitch comes possibly later, but will still occur)
|  >  (c) ditch principle and use even lower granularity - milliseconds (jiffies seems like a natural match)
|  > 
|  > My personal favourite is (c).
|  
|  I think that we should provide the best granularity available we can
|  while not impacting non DCCP code (remember the net_enable_timestamp()
|  case?). CCID3 probably is what people will try first, I guess.
|
You are fully right on this one - when thinking again about (c) I thought this is
nonsense, especially since new CCIDs will come and good resolution is available.
Fully agree with you.
  

|  Just checked and dccp_insert_option_timestamp already is called only
|  from two places: ccid3 and from dccp_insert_options when sending the
|  REQUEST packet, also on behalf of ccid3, I'll check if we can somehow
|  shift this option insertion in the REQUEST packet entirely to the
|  CCID3 code.
To be honest, I wasn't sure where to place this and timer.c seemed to be a generic 
place. It may be that other code (as in your comment regarding CCID2) wants
to do a timestamp, so moving it to the CCID code could restrict this.

Aside: I had another thought recently - that of providing an `RTT' field
in the dccp_sk. In the spec there are numerous references to `if x does not happen
for y RTTs, then do z'. This field could be initialised with the default RTT from 
section 3.4 of RFC 4340 (200msec), so that it is there if some code needs it.

  
|  Humm, there is also elapsed time in dccp_timestamp_echo, but that is a
|  delta, so we should have enough space on 32 bits... but because of that
|  we need to do timestamping on dccp_parse_options and not in the CCID
|  code that needs this... i.e. if we want to avoid having dccps_epoch in
|  dccp_sock we might as well get rid of dccps_timestamp_time and
|  dccps_timestamp_echo, shifting it to some other struct that would be
|  inserted on any CCID that wants to use these timestamping.
I haven't checked this but to me the dccps_timestamp_time seemed a very good
idea for measuring the elapsed time delta. I thought that this was pretty well
done.

I am taking your comments home, I will try to figure out if there is a better alternative
to the 11.9 hours glitch (which could happen before 11.9 hours have passed).

  
|  Checking RFC4341 (CCID2):
|  
|     6. The sender estimates round-trip times, either through keeping
|        track of acknowledgement round-trip times as TCP does or through
|        explicit Timestamp options, and calculates a TimeOut (TO) value
|        much as the RTO (Retransmit Timeout) is calculated in TCP.  
There is a trap here. I have been thinking about the same stuff when working on CCID3.
It reads very simple, but opens a can of worms. When looking at the RFC 1323 code for
this kind of timestamping, one can see that there are quite a few cases where this simple
notion of RTT sampling can go very wrong. And they also did an Internet Draft which corrected
the errors from the RFC 1323 spec for this (it is referenced in the TCP code somewhere).
I'd take my hat off to anyone able to turn this into a robust algorithm, I think this is not
trivial do get right. The way it is done in CCID3 is robust IMHO, i.e. take one timestamp
when the packet leaves, take another when the reply comes and compute the difference.