: Cheaper & smaller timestamping

[DCCP]: Cheaper & smaller timestamping

Currently dccp_timestamp calculates timestamps relative to an offset computed at initialisation time. This patch reduces the cost of timestamping by removing the offset computation. This affords the advantages that

* there are now fewer instructions per single timestamp;
* the size of the dccp_sock becomes smaller (minus @dccps_epoch).

(NB: Using a reference epoch is not strictly necessary, since all known timestamping
operations in DCCP only need relative time differences, but not absolute time. I have tested this patch for a while on different platforms, found no problems.)

---
 include/linux/dccp.h                |    2 --
 net/dccp/ackvec.c                   |    4 ++--
 net/dccp/ccids/ccid3.c              |   18 +++++++++---------
 net/dccp/ccids/lib/packet_history.h |    2 +-
 net/dccp/dccp.h                     |    2 --
 net/dccp/input.c                    |    2 +-
 net/dccp/minisocks.c                |    1 -
 net/dccp/options.c                  |   22 +++-------------------
 net/dccp/proto.c                    |    1 -
 9 files changed, 16 insertions(+), 38 deletions(-)

@@ -476,7 +476,6 @@ struct dccp_ackvec;
  * @dccps_hc_rx_ccid -
  * @dccps_hc_tx_ccid -
  * @dccps_options_received -
- * @dccps_epoch -
  * @dccps_role - Role of this sock, one of %dccp_role
  * @dccps_hc_rx_insert_options -
  * @dccps_hc_tx_insert_options -

@@ -512,7 +511,6 @@ struct dccp_sock {
 	struct ccid			*dccps_hc_rx_ccid;
 	struct ccid			*dccps_hc_tx_ccid;
 	struct dccp_options_received	dccps_options_received;
-	struct timeval			dccps_epoch;
 	enum dccp_role			dccps_role:2;
 	__u8				dccps_hc_rx_insert_options:1;
 	__u8				dccps_hc_tx_insert_options:1;

@@ -158,7 +158,7 @@ int dccp_parse_options(struct sock *sk, 
 			opt_recv->dccpor_timestamp = ntohl(*(__be32 *)value);
 
 			dp->dccps_timestamp_echo = opt_recv->dccpor_timestamp;
-			dccp_timestamp(sk, &dp->dccps_timestamp_time);
+			do_gettimeofday(&dp->dccps_timestamp_time);
 
 			dccp_pr_debug("%s rx opt: TIMESTAMP=%u, ackno=%llu\n",
 				      dccp_role(sk), opt_recv->dccpor_timestamp,

@@ -370,28 +370,12 @@ int dccp_insert_option_elapsed_time(stru
 
 EXPORT_SYMBOL_GPL(dccp_insert_option_elapsed_time);
 
-void dccp_timestamp(const struct sock *sk, struct timeval *tv)
-{
-	const struct dccp_sock *dp = dccp_sk(sk);
-
-	do_gettimeofday(tv);
-	tv->tv_sec  -= dp->dccps_epoch.tv_sec;
-	tv->tv_usec -= dp->dccps_epoch.tv_usec;
-
-	while (tv->tv_usec < 0) {
-		tv->tv_sec--;
-		tv->tv_usec += USEC_PER_SEC;
-	}
-}
-
-EXPORT_SYMBOL_GPL(dccp_timestamp);
-
 int dccp_insert_option_timestamp(struct sock *sk, struct sk_buff *skb)
 {
 	struct timeval tv;
 	__be32 now;
 
-	dccp_timestamp(sk, &tv);
+	do_gettimeofday(&tv);
 	now = htonl(timeval_usecs(&tv) / 10);
 	/* 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 */

@@ -411,7 +395,7 @@ static int dccp_insert_option_timestamp_
 	int len, elapsed_time_len;
 	unsigned char *to;
 
-	dccp_timestamp(sk, &now);
+	do_gettimeofday(&now);
 	elapsed_time = timeval_delta(&now, &dp->dccps_timestamp_time) / 10;
 	elapsed_time_len = dccp_elapsed_time_len(elapsed_time);
 	len = 6 + elapsed_time_len;

@@ -402,8 +402,6 @@ extern int dccp_insert_option(struct soc
 			       unsigned char option,
 			       const void *value, unsigned char len);
 
-extern void dccp_timestamp(const struct sock *sk, struct timeval *tv);
-
 static inline suseconds_t timeval_usecs(const struct timeval *tv)
 {
 	return tv->tv_sec * USEC_PER_SEC + tv->tv_usec;

@@ -82,7 +82,7 @@ int dccp_insert_option_ackvec(struct soc
 	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
 		return -1;
 
-	dccp_timestamp(sk, &now);
+	do_gettimeofday(&now);
 	elapsed_time = timeval_delta(&now, &av->dccpav_time) / 10;
 
 	if (elapsed_time != 0 &&

@@ -321,7 +321,7 @@ int dccp_ackvec_add(struct dccp_ackvec *
 	}
 
 	av->dccpav_buf_ackno = ackno;
-	dccp_timestamp(sk, &av->dccpav_time);
+	do_gettimeofday(&av->dccpav_time);
 out:
 	return 0;
 

@@ -273,7 +273,7 @@ static void ccid3_hc_tx_no_feedback_time
 							      (2 * TFRC_T_MBI));
 
 			if (hctx->ccid3hctx_p = 0)
-				dccp_timestamp(sk, &now);
+				do_gettimeofday(&now);
 		} else {
 			hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc;
 			hctx->ccid3hctx_x_recv <<= 4;

@@ -325,7 +325,7 @@ static int ccid3_hc_tx_send_packet(struc
 	if (unlikely(skb->len = 0))
 		return -EBADMSG;
 
-	dccp_timestamp(sk, &now);
+	do_gettimeofday(&now);
 
 	switch (hctx->ccid3hctx_state) {
 	case TFRC_SSTATE_NO_SENT:

@@ -418,7 +418,7 @@ static void ccid3_hc_tx_packet_sent(stru
 	}
 	dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, packet);
 
-	dccp_timestamp(sk, &now);
+	do_gettimeofday(&now);
 	packet->dccphtx_tstamp = now;
 	packet->dccphtx_seqno  = dccp_sk(sk)->dccps_gss;
 	packet->dccphtx_rtt    = hctx->ccid3hctx_rtt;

@@ -469,7 +469,7 @@ static void ccid3_hc_tx_packet_recv(stru
 		else				       /* can not exceed 100% */
 			hctx->ccid3hctx_p = 1000000 / pinv;
 
-		dccp_timestamp(sk, &now);
+		do_gettimeofday(&now);
 
 		/*
 		 * Calculate new round trip sample as per [RFC 3448, 4.3] by

@@ -751,7 +751,7 @@ static void ccid3_hc_rx_send_feedback(st
 
 	ccid3_pr_debug("%s(%p) - entry \n", dccp_role(sk), sk);
 
-	dccp_timestamp(sk, &now);
+	do_gettimeofday(&now);
 
 	switch (hcrx->ccid3hcrx_state) {
 	case TFRC_RSTATE_NO_DATA:

@@ -903,7 +903,7 @@ found:
 		return ~0;
 	}
 
-	dccp_timestamp(sk, &tstamp);
+	do_gettimeofday(&tstamp);
 	delta = timeval_delta(&tstamp, &hcrx->ccid3hcrx_tstamp_last_feedback);
 	DCCP_BUG_ON(delta <= 0);
 

@@ -1050,7 +1050,7 @@ static void ccid3_hc_rx_packet_recv(stru
 		if (opt_recv->dccpor_timestamp_echo = 0)
 			break;
 		rtt_prev = hcrx->ccid3hcrx_rtt;
-		dccp_timestamp(sk, &now);
+		do_gettimeofday(&now);
 		r_sample = dccp_sample_rtt(sk, &now, NULL);
 
 		if (hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA)

@@ -1099,7 +1099,7 @@ static void ccid3_hc_rx_packet_recv(stru
 		if (loss)
 			break;
 
-		dccp_timestamp(sk, &now);
+		do_gettimeofday(&now);
 		if ((timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) -
 		     (suseconds_t)hcrx->ccid3hcrx_rtt) >= 0) {
 			hcrx->ccid3hcrx_tstamp_last_ack = now;

@@ -1142,7 +1142,7 @@ static int ccid3_hc_rx_init(struct ccid 
 	hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
 	INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
 	INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist);
-	dccp_timestamp(sk, &hcrx->ccid3hcrx_tstamp_last_ack);
+	do_gettimeofday(&hcrx->ccid3hcrx_tstamp_last_ack);
 	hcrx->ccid3hcrx_tstamp_last_feedback = hcrx->ccid3hcrx_tstamp_last_ack;
 	hcrx->ccid3hcrx_s   = 0;
 	hcrx->ccid3hcrx_rtt = 0;

@@ -151,7 +151,7 @@ static inline struct dccp_rx_hist_entry 
 		entry->dccphrx_ccval = dh->dccph_ccval;
 		entry->dccphrx_type  = dh->dccph_type;
 		entry->dccphrx_ndp   = ndp;
-		dccp_timestamp(sk, &entry->dccphrx_tstamp);
+		do_gettimeofday(&entry->dccphrx_tstamp);
 	}
 
 	return entry;

@@ -112,7 +112,6 @@ struct sock *dccp_create_openreq_child(s
 		newdp->dccps_service_list  = NULL;
 		newdp->dccps_service	   = dreq->dreq_service;
 		newicsk->icsk_rto	   = DCCP_TIMEOUT_INIT;
-		do_gettimeofday(&newdp->dccps_epoch);
 
 		if (dccp_feat_clone(sk, newsk))
 			goto out_free;

@@ -172,7 +172,6 @@ int dccp_init_sock(struct sock *sk, cons
 	struct inet_connection_sock *icsk = inet_csk(sk);
 
 	dccp_minisock_init(&dp->dccps_minisock);
-	do_gettimeofday(&dp->dccps_epoch);
 
 	/*
 	 * FIXME: We're hardcoding the CCID, and doing this at this point makes

@@ -304,7 +304,7 @@ static int dccp_rcv_request_sent_state_p
 		if (dp->dccps_options_received.dccpor_timestamp_echo) {
 			struct timeval now;
 
-			dccp_timestamp(sk, &now);
+			do_gettimeofday(&now);
 			dp->dccps_syn_rtt = dccp_sample_rtt(sk, &now, NULL);
 		}
 

A couple of comments though:
- this is how I had the code originally in many cases and Arnaldo changed - can't remember why.
- we should be looking at using the new ktime as monotonic but that can be a task for another time.

Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

| > [DCCP]: Cheaper & smaller timestamping

|  A couple of comments though:
|  - this is how I had the code originally in many cases and Arnaldo
|  changed - can't remember why.

Arnaldo's code uses a reference point, the skb_get_timestamp() also did that. May be useful against old incarnations across reboots.

|  - we should be looking at using the new ktime as monotonic but that
|  can be a task for another time.

Excellent idea, this may allow to make CCID3 more precise.

By sheer magic, skb_get_timestamp does this already, as I just saw:

static inline void skb_get_timestamp(const struct sk_buff *skb, struct timeval *stamp)

{
	*stamp = ktime_to_timeval(skb->tstamp);
}

so we only need to replace the do_gettimeofday() at some time.

I have another idea with regard to timestamps: the field
dccp_inetconnection.icsk_ack.lrcvtime
takes an __u32 timestamp - we could use this for the DCCP timestamp/timestamp echos, which are 4 bytes (currently this is done for initial SYN RTT).

I got to this cset now in today's merge session, the cset that did that was:

b0e567806d16586629468c824dfb2e71155df7da

Comment was, unfortunately, not so clear:

----
[acme@mica net-2.6.22]$ git-show b0e567806d16586629468c824dfb2e71155df7da commit b0e567806d16586629468c824dfb2e71155df7da

Author: Arnaldo Carvalho de Melo <[email protected]>
Date:   Fri Sep 9 02:38:35 2005 -0300

[DCCP] Introduce dccp_timestamp

To start the timestamps with 0.0ms, easing the integer maths in
the CCIDs, this
probably will be reworked to use the to be introduced struct timeval_offset infrastructure out of skb_get_timestamp, etc.

---

What are the architectures you've been testing? All 64 bits? IIRC the problem was related to overflows, suseconds_t is unsigned long, so 32 bits on i386...

Yes, skb_get_timestamp seems to be the right thing to do, but now I'm uneasy about applying the patch that essentially reverts b0e567806d16586629468c824dfb2e71155df7da, will try not applying it and applying the followup patches, will report the results soon.

- Arnaldo

OK, you did the conversion, applying it.

- Arnaldo

Quoting Arnaldo Carvalho de Melo:

|  On 4/2/07, Gerrit Renker <[email protected]> wrote:
|  > |  > [DCCP]: Cheaper & smaller timestamping
|  >
|  > |  A couple of comments though:
|  > |  - this is how I had the code originally in many cases and Arnaldo
|  > |  changed - can't remember why.
|  > Arnaldo's code uses a reference point, the skb_get_timestamp() also did
|  > that. May be useful against old incarnations across reboots.
|  
|  I got to this cset now in today's merge session, the cset that did that was:
|  
|  b0e567806d16586629468c824dfb2e71155df7da
|  
|  Comment was, unfortunately, not so clear:
|  
|  ----
|  [acme@mica net-2.6.22]$ git-show b0e567806d16586629468c824dfb2e71155df7da
|  commit b0e567806d16586629468c824dfb2e71155df7da
|  Author: Arnaldo Carvalho de Melo <[email protected]>
|  Date:   Fri Sep 9 02:38:35 2005 -0300
|  
|      [DCCP] Introduce dccp_timestamp
|  
|      To start the timestamps with 0.0ms, easing the integer maths in
|  the CCIDs, this
|      probably will be reworked to use the to be introduced struct timeval_offset
|      infrastructure out of skb_get_timestamp, etc.
|  
|      Signed-off-by: Arnaldo Carvalho de Melo <[email protected]>
|  ---
|  
|  What are the architectures you've been testing? All 64 bits? IIRC the
|  problem was related to overflows, suseconds_t is unsigned long, so 32
|  bits on i386...

I have tested on various i386 instances (where it is long') and on sparc64 (where it is int', as in parisc). I was just calculating - there is indeed a chance to produce overflow, since we add in timeval_add_usecs (since it is a signed type, the same problem seems to reappear in timeval_sub_usecs).

I don't have accurate figures at the moment with regard to overflow, but I assume that it is better to revert this patch?

There is a related question - with the new timesystem, should we convert to __get_realtime_clock_ts(), as the comment above do_gettimeofday() says in kernel/timer.c ?

I would be glad for clarification, since there are quite a few patches to update.

Cheers.

I'd say leave the dccp_timestamp alone for now, I have to read a bit more on the new time system and what was done on the net schedulers, etc before being able to say something meaningful on this aspect.

- Arnaldo

Quoting Arnaldo Carvalho de Melo:

|  > I have tested on various i386 instances (where it is `long') and on sparc64 (where it is `int', as
|  > in parisc).  I was just calculating - there is indeed a chance to produce overflow, since we add
|  > in timeval_add_usecs (since it is a signed type, the same problem seems to reappear in timeval_sub_usecs).
|  >
|  > I don't have accurate figures at the moment with regard to overflow, but I assume that it is better to revert
|  > this patch?
|  >
|  > There is a related question  - with the new timesystem, should we convert to __get_realtime_clock_ts(), as
|  > the comment above do_gettimeofday() says in kernel/timer.c ?
|  >
|  > I would be glad for clarification, since there are quite a few patches to update.
|  
|  I'd say leave the dccp_timestamp alone for now, I have to read a bit
|  more on the new time system and what was done on the net schedulers,
|  etc before being able to say something meaningful on this aspect.
|  

Just to be on the safe side then I will revert this patch 4/25 so that everything again uses dccp_epoch, ok?

Yes

- Arnaldo