[PATCH 0/8] [DCCP]: Updates and fixes to ensure code works with recent changes

[PATCH 0/8] [DCCP]: Updates and fixes to ensure code works with recent changes

[Gerrit Renker]

Some of the recent changes in 2.6.25 cause problems with the existing implementation (i.e. break
the code). This patch set therefore provides fixes and resubmits one subsequent patch which
has not been considered so far, but which is part of the tfrc_lib package.

  Patch #1: Performs whitespace cleanups.
  Patch #2: Migrates all loss interval / packet history initialisation code into tfrc.c.
  Patch #3: Removes two unused functions/function calls that have become obsolete now.
  Patch #4: Splits rx_hist_add_packet() into its original constituents -- they are needed.
  Patch #5: Restores the parts of the macro/inline conversion that broke the algorithm.
  Patch #6: Is a v2 patch - the Loss Intervals code, now updated to work with the recent changes.
  Patch #7: Reverts hiding inlines which are needed by the calling CCID module.
  Patch #8: Also a patch v2 - shows how all the new stuff is integrated to work with CCID3.

The code compiles cleanly, all patches have been uploaded to the test tree (backported from 2.6.25),
  git://eden-feed.erg.abdn.ac.uk/dccp_exp 	[dccp]

So far only a few quick bandwidth tests have been performed. These merely confirm that the stack
does not crash. Since most of this patch set deals with loss detection and re-ordering, some more
detailed tests are needed to ensure that the code, as before, deals well with loss, reordering,
and duplication (this requires at least one NetEm box).

Updates to the CCID4 subtree need to be suspended for a few days. There are too many fiddly changes
all over the place; until we understand exactly what is going on and if there has been a
regression, it is not a good idea to track everything.

[PATCH 1/8] [TFRC]: Whitespace cleanups

[Gerrit Renker]

Just some tidy-ups to keep git/quilt happy. Also moved up the
comment "Receiver routines" above the first occurrence of RX
history routines.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/ccid3.c              |   16 ++++++++--------
 net/dccp/ccids/lib/loss_interval.c  |    2 +-
 net/dccp/ccids/lib/packet_history.c |   12 ++++++------
 3 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
index faacffa..a5246f7 100644
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -780,7 +780,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 			 */
 		}
 		goto update_records;
- 	}
+	}
 
 	if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb))
 		return; /* done receiving */
@@ -792,7 +792,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 		 */
 		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload, 9);
 		hcrx->ccid3hcrx_bytes_recv += payload;
- 	}
+	}
 
 	/*
 	 * Handle pending losses and otherwise check for new loss
@@ -808,11 +808,11 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 
 	if (list_empty(&hcrx->ccid3hcrx_li_hist)) {  /* no loss so far: p = 0 */
 		const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_hist, skb);
- 		/*
- 		 * Empty loss history: no loss so far, hence p stays 0.
- 		 * Sample RTT values, since an RTT estimate is required for the
- 		 * computation of p when the first loss occurs; RFC 3448, 6.3.1.
- 		 */
+		/*
+		 * Empty loss history: no loss so far, hence p stays 0.
+		 * Sample RTT values, since an RTT estimate is required for the
+		 * computation of p when the first loss occurs; RFC 3448, 6.3.1.
+		 */
 		if (sample != 0)
 			hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9);
 	}
@@ -823,7 +823,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 	if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
 		do_feedback = CCID3_FBACK_PERIODIC;
 
-update_records:	
+update_records:
 	tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);
 
 	if (do_feedback)
diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c
index 7e0714a..c0a933a 100644
--- a/net/dccp/ccids/lib/loss_interval.c
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -131,7 +131,7 @@ static u32 dccp_li_calc_first_li(struct sock *sk,
 {
 /*
  * FIXME:
- * Will be rewritten in the upcoming new loss intervals code. 
+ * Will be rewritten in the upcoming new loss intervals code.
  * Has to be commented ou because it relies on the old rx history
  * data structures
  */
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index e197389..54cd23e 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -114,6 +114,11 @@ u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno,
 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt);
 
 
+/*
+ * 	Receiver History Routines
+ */
+static struct kmem_cache *tfrc_rx_hist_slab;
+
 /**
  * tfrc_rx_hist_index - index to reach n-th entry after loss_start
  */
@@ -131,11 +136,6 @@ static inline struct tfrc_rx_hist_entry *
 	return h->ring[tfrc_rx_hist_index(h, h->loss_count)];
 }
 
-/*
- * 	Receiver History Routines
- */
-static struct kmem_cache *tfrc_rx_hist_slab;
-
 void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 			     const struct sk_buff *skb,
 			     const u32 ndp)
@@ -278,7 +278,7 @@ u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb)
 {
 	u32 sample = 0,
 	    delta_v = SUB16(dccp_hdr(skb)->dccph_ccval,
-	    		    tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
+			    tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
 
 	if (delta_v < 1 || delta_v > 4) {	/* unsuitable CCVal delta */
 		if (h->rtt_sample_prev == 2) {	/* previous candidate stored */

[PATCH 2/8] [TFRC]: Put RX/TX initialisation into tfrc.c

[Gerrit Renker]

This separates RX/TX initialisation and puts all packet history / loss intervals
initialisation into tfrc.c.
The organisation is uniform: slab declaration -> {rx,tx}_init() -> {rx,tx}_exit()

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/packet_history.c |   68 ++++++++++++++++------------------
 net/dccp/ccids/lib/tfrc.c           |   31 ++++++++++++----
 2 files changed, 55 insertions(+), 44 deletions(-)

diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index 54cd23e..af0db71 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -57,6 +57,22 @@ struct tfrc_tx_hist_entry {
  */
 static struct kmem_cache *tfrc_tx_hist_slab;
 
+int __init tfrc_tx_packet_history_init(void)
+{
+	tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist",
+					      sizeof(struct tfrc_tx_hist_entry),
+					      0, SLAB_HWCACHE_ALIGN, NULL);
+	return tfrc_tx_hist_slab == NULL ? -ENOBUFS : 0;
+}
+
+void __exit tfrc_tx_packet_history_exit(void)
+{
+	if (tfrc_tx_hist_slab != NULL) {
+		kmem_cache_destroy(tfrc_tx_hist_slab);
+		tfrc_tx_hist_slab = NULL;
+	}
+}
+
 static struct tfrc_tx_hist_entry *
 	tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno)
 {
@@ -119,6 +135,22 @@ EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt);
  */
 static struct kmem_cache *tfrc_rx_hist_slab;
 
+int __init tfrc_rx_packet_history_init(void)
+{
+	tfrc_rx_hist_slab = kmem_cache_create("tfrc_rxh_cache",
+					      sizeof(struct tfrc_rx_hist_entry),
+					      0, SLAB_HWCACHE_ALIGN, NULL);
+	return tfrc_rx_hist_slab == NULL ? -ENOBUFS : 0;
+}
+
+void __exit tfrc_rx_packet_history_exit(void)
+{
+	if (tfrc_rx_hist_slab != NULL) {
+		kmem_cache_destroy(tfrc_rx_hist_slab);
+		tfrc_rx_hist_slab = NULL;
+	}
+}
+
 /**
  * tfrc_rx_hist_index - index to reach n-th entry after loss_start
  */
@@ -321,39 +353,3 @@ keep_ref_for_next_time:
 	return sample;
 }
 EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt);
-
-__init int packet_history_init(void)
-{
-	tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist",
-					      sizeof(struct tfrc_tx_hist_entry), 0,
-					      SLAB_HWCACHE_ALIGN, NULL);
-	if (tfrc_tx_hist_slab == NULL)
-		goto out_err;
-
-	tfrc_rx_hist_slab = kmem_cache_create("tfrc_rx_hist",
-					      sizeof(struct tfrc_rx_hist_entry), 0,
-					      SLAB_HWCACHE_ALIGN, NULL);
-	if (tfrc_rx_hist_slab == NULL)
-		goto out_free_tx;
-
-	return 0;
-
-out_free_tx:
-	kmem_cache_destroy(tfrc_tx_hist_slab);
-	tfrc_tx_hist_slab = NULL;
-out_err:
-	return -ENOBUFS;
-}
-
-void packet_history_exit(void)
-{
-	if (tfrc_tx_hist_slab != NULL) {
-		kmem_cache_destroy(tfrc_tx_hist_slab);
-		tfrc_tx_hist_slab = NULL;
-	}
-
-	if (tfrc_rx_hist_slab != NULL) {
-		kmem_cache_destroy(tfrc_rx_hist_slab);
-		tfrc_rx_hist_slab = NULL;
-	}
-}
diff --git a/net/dccp/ccids/lib/tfrc.c b/net/dccp/ccids/lib/tfrc.c
index 3a7a183..20763fa 100644
--- a/net/dccp/ccids/lib/tfrc.c
+++ b/net/dccp/ccids/lib/tfrc.c
@@ -14,27 +14,42 @@ module_param(tfrc_debug, bool, 0444);
 MODULE_PARM_DESC(tfrc_debug, "Enable debug messages");
 #endif
 
+extern int  tfrc_tx_packet_history_init(void);
+extern void tfrc_tx_packet_history_exit(void);
+extern int  tfrc_rx_packet_history_init(void);
+extern void tfrc_rx_packet_history_exit(void);
+
 extern int  dccp_li_init(void);
 extern void dccp_li_exit(void);
-extern int packet_history_init(void);
-extern void packet_history_exit(void);
 
 static int __init tfrc_module_init(void)
 {
 	int rc = dccp_li_init();
 
-	if (rc == 0) {
-		rc = packet_history_init();
-		if (rc != 0)
-			dccp_li_exit();
-	}
+	if (rc)
+		goto out;
+
+	rc = tfrc_tx_packet_history_init();
+	if (rc)
+		goto out_free_loss_intervals;
 
+	rc = tfrc_rx_packet_history_init();
+	if (rc)
+		goto out_free_tx_history;
+	return 0;
+
+out_free_tx_history:
+	tfrc_tx_packet_history_exit();
+out_free_loss_intervals:
+	dccp_li_exit();
+out:
 	return rc;
 }
 
 static void __exit tfrc_module_exit(void)
 {
-	packet_history_exit();
+	tfrc_rx_packet_history_exit();
+	tfrc_tx_packet_history_exit();
 	dccp_li_exit();
 }
 

[PATCH 3/8] [TFRC/CCID3]: Remove now unused functions / function calls

[Gerrit Renker]

This removes two things which now have become redundant:
 1. The function tfrc_rx_hist_entry_delete() is no longer referenced anywhere.
 2. The CCID3 HC-receiver still inserted timestamps, but received timestamps
    are not parsed/referenced/used by the HC-sender, it serves no function.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/ccid3.c              |    3 +--
 net/dccp/ccids/lib/packet_history.c |    5 -----
 2 files changed, 1 insertions(+), 7 deletions(-)

diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
index a5246f7..60fcb31 100644
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -750,8 +750,7 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
 	x_recv = htonl(hcrx->ccid3hcrx_x_recv);
 	pinv   = htonl(hcrx->ccid3hcrx_pinv);
 
-	if (dccp_insert_option_timestamp(sk, skb) ||
-	    dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
+	if (dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
 			       &pinv, sizeof(pinv)) ||
 	    dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
 			       &x_recv, sizeof(x_recv)))
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index af0db71..4d37396 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -183,11 +183,6 @@ void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 }
 EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet);
 
-static inline void tfrc_rx_hist_entry_delete(struct tfrc_rx_hist_entry *entry)
-{
-	kmem_cache_free(tfrc_rx_hist_slab, entry);
-}
-
 /**
  * tfrc_rx_hist_entry - return the n-th history entry after loss_start
  */

[PATCH 4/8] [TFRC]: Need separate entry_from_skb routine

[Gerrit Renker]

This again separates tfrc_rx_hist_packet() from tfrc_rx_hist_entry_from_skb(), which
was the format used in the original patch submission. The reason for this is the
requirement -- used by the subsequent patches -- to be able to insert a newly arrived
skb in arbitrary places within the ringbuffer history.

The add_packet() function is only a special case of this usage: it inserts always
at the front, and thus updates the highest-received sequence number. That has been
the main reason why it was originally called tfrc_rx_hist_update() --  the old name
reflected better what the function did.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/packet_history.c |   35 ++++++++++++++++++++---------------
 1 files changed, 20 insertions(+), 15 deletions(-)

diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index 4d37396..6256bec 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -168,21 +168,6 @@ static inline struct tfrc_rx_hist_entry *
 	return h->ring[tfrc_rx_hist_index(h, h->loss_count)];
 }
 
-void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
-			     const struct sk_buff *skb,
-			     const u32 ndp)
-{
-	struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h);
-	const struct dccp_hdr *dh = dccp_hdr(skb);
-
-	entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
-	entry->tfrchrx_ccval = dh->dccph_ccval;
-	entry->tfrchrx_type  = dh->dccph_type;
-	entry->tfrchrx_ndp   = ndp;
-	entry->tfrchrx_tstamp = ktime_get_real();
-}
-EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet);
-
 /**
  * tfrc_rx_hist_entry - return the n-th history entry after loss_start
  */
@@ -218,6 +203,26 @@ int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
 }
 EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate);
 
+static void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry,
+					const struct sk_buff *skb, u32 ndp)
+{
+	const struct dccp_hdr *dh = dccp_hdr(skb);
+
+	entry->tfrchrx_seqno  = DCCP_SKB_CB(skb)->dccpd_seq;
+	entry->tfrchrx_ccval  = dh->dccph_ccval;
+	entry->tfrchrx_type   = dh->dccph_type;
+	entry->tfrchrx_ndp    = ndp;
+	entry->tfrchrx_tstamp = ktime_get_real();
+}
+
+/* commit packet details of skb to history (record highest received seqno) */
+void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
+			     const struct sk_buff *skb, u32 ndp)
+{
+	tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_last_rcv(h), skb, ndp);
+}
+EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet);
+
 /* initialise loss detection and disable RTT sampling */
 static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h)
 {

[PATCH 5/8] [TFRC]: Loss interval code needs the macros/inlines that were moved

[Gerrit Renker]

This moves the inlines (which were previously declared as macros) back into packet_history.h since
the loss detection code needs to be able to read entries from the RX history in order to create the
relevant loss entries: it needs at least tfrc_rx_hist_loss_prev() and tfrc_rx_hist_last_rcv(), which
in turn require the definition of the other inlines (macros).

Additionally, inn one case the use of inlines instead of a macro broke the algorithm: rx_hist_swap()
(introduced in next patch) needs to be able to swap the history entries; when using an inline returning
a pointer instead, one gets compilation errors such as:

  distcc[24516] ERROR: compile /root/.ccache/packet_his.tmp.aspire.home.net.24512.i on _tiptop failed
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__one_after_loss':
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:266: error: lvalue required as unary '&' operand
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:267: error: lvalue required as unary '&' operand
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__two_after_loss':
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:298: error: lvalue required as unary '&' operand
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:299: error: lvalue required as unary '&' operand
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:336: error: lvalue required as unary '&' operand
  /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:337: error: lvalue required as unary '&' operand
  make[4]: *** [net/dccp/ccids/lib/packet_history.o] Error 1
  make[3]: *** [net/dccp/ccids/lib] Error 2
  make[2]: *** [net/dccp/ccids] Error 2
  make[1]: *** [net/dccp/] Error 2
  make: *** [sub-make] Error 2

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/packet_history.c |   37 +----------------------------------
 net/dccp/ccids/lib/packet_history.h |   32 ++++++++++++++++++++++++++++++
 2 files changed, 33 insertions(+), 36 deletions(-)

diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index 6256bec..428636e 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -151,41 +151,6 @@ void __exit tfrc_rx_packet_history_exit(void)
 	}
 }
 
-/**
- * tfrc_rx_hist_index - index to reach n-th entry after loss_start
- */
-static inline u8 tfrc_rx_hist_index(const struct tfrc_rx_hist *h, const u8 n)
-{
-	return (h->loss_start + n) & TFRC_NDUPACK;
-}
-
-/**
- * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far
- */
-static inline struct tfrc_rx_hist_entry *
-			tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist *h)
-{
-	return h->ring[tfrc_rx_hist_index(h, h->loss_count)];
-}
-
-/**
- * tfrc_rx_hist_entry - return the n-th history entry after loss_start
- */
-static inline struct tfrc_rx_hist_entry *
-		tfrc_rx_hist_entry(const struct tfrc_rx_hist *h, const u8 n)
-{
-	return h->ring[tfrc_rx_hist_index(h, n)];
-}
-
-/**
- * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected
- */
-static inline struct tfrc_rx_hist_entry *
-			tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist *h)
-{
-	return h->ring[h->loss_start];
-}
-
 /* has the packet contained in skb been seen before? */
 int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
 {
@@ -196,7 +161,7 @@ int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
 		return 1;
 
 	for (i = 1; i <= h->loss_count; i++)
-		if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq)
+		if (TFRC_RX_HIST_ENTRY(h, i)->tfrchrx_seqno == seq)
 			return 1;
 
 	return 0;
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index 3dfd182..6ea25cd 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -84,6 +84,38 @@ struct tfrc_rx_hist {
 #define rtt_sample_prev		  loss_start
 };
 
+/**
+ * tfrc_rx_hist_index - index to reach n-th entry after loss_start
+ */
+static inline u8 tfrc_rx_hist_index(const struct tfrc_rx_hist *h, const u8 n)
+{
+	return (h->loss_start + n) & TFRC_NDUPACK;
+}
+
+/**
+ * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far
+ */
+static inline struct tfrc_rx_hist_entry *
+			tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist *h)
+{
+	return h->ring[tfrc_rx_hist_index(h, h->loss_count)];
+}
+
+/**
+ * tfrc_rx_hist_entry - return the n-th history entry after loss_start
+ * This has to be a macro since rx_hist_swap needs to be able to swap entries.
+ */
+#define TFRC_RX_HIST_ENTRY(h, n)	((h)->ring[tfrc_rx_hist_index(h, n)])
+
+/**
+ * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected
+ */
+static inline struct tfrc_rx_hist_entry *
+			tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist *h)
+{
+	return h->ring[h->loss_start];
+}
+
 extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 				    const struct sk_buff *skb, const u32 ndp);
 

[PATCH 6/8] [PATCH v2] [TFRC]: Ringbuffer to track loss interval history

[Gerrit Renker]

A ringbuffer-based implementation of loss interval history is easier to
maintain, allocate, and update.

Details:
 * access to the Loss Interval Records via macro wrappers (with safety checks);
 * simplified, on-demand allocation of entries (no extra memory consumption on
   lossless links); cache allocation is local to the module / exported as service;
 * provision of RFC-compliant algorithm to re-compute average loss interval;
 * provision of comprehensive, new loss detection algorithm
 	- support for all cases of loss, including re-ordered/duplicate packets;
 	- waiting for NDUPACK=3 packets to fill the hole;
	- updating loss records when a late-arriving packet fills a hole.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
---
 net/dccp/ccids/lib/loss_interval.c  |  158 ++++++++++++++++++++++++++-
 net/dccp/ccids/lib/loss_interval.h  |   58 ++++++++++-
 net/dccp/ccids/lib/packet_history.c |  201 +++++++++++++++++++++++++++++++++++
 net/dccp/ccids/lib/packet_history.h |   11 ++-
 net/dccp/ccids/lib/tfrc.h           |    3 +
 5 files changed, 421 insertions(+), 10 deletions(-)

diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c
index c0a933a..b0e59fb 100644
--- a/net/dccp/ccids/lib/loss_interval.c
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -1,6 +1,7 @@
 /*
  *  net/dccp/ccids/lib/loss_interval.c
  *
+ *  Copyright (c) 2007   The University of Aberdeen, Scotland, UK
  *  Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
  *  Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
@@ -10,12 +11,7 @@
  *  the Free Software Foundation; either version 2 of the License, or
  *  (at your option) any later version.
  */
-
-#include <linux/module.h>
 #include <net/sock.h>
-#include "../../dccp.h"
-#include "loss_interval.h"
-#include "packet_history.h"
 #include "tfrc.h"
 
 #define DCCP_LI_HIST_IVAL_F_LENGTH  8
@@ -27,6 +23,51 @@ struct dccp_li_hist_entry {
 	u32		 dccplih_interval;
 };
 
+static struct kmem_cache  *tfrc_lh_slab  __read_mostly;
+/* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */
+static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 };
+
+/*
+ * Access macros: These require that at least one entry is present in lh,
+ * and implement array semantics (0 is first, n-1 is the last of n entries).
+ */
+#define __lih_index(lh, n)	LIH_INDEX((lh)->counter - (n) - 1)
+#define __lih_entry(lh, n)	(lh)->ring[__lih_index(lh, n)]
+#define __curr_entry(lh)	(lh)->ring[LIH_INDEX((lh)->counter - 1)]
+#define __next_entry(lh)	(lh)->ring[LIH_INDEX((lh)->counter)]
+
+/* given i with 0 <= i <= k, return I_i as per the rfc3448bis notation */
+static inline u32 tfrc_lh_get_interval(struct tfrc_loss_hist *lh, u8 i)
+{
+	BUG_ON(i >= lh->counter);
+	return __lih_entry(lh, i)->li_length;
+}
+
+static inline struct tfrc_loss_interval *tfrc_lh_peek(struct tfrc_loss_hist *lh)
+{
+	return lh->counter ? __curr_entry(lh) : NULL;
+}
+
+/*
+ *	On-demand allocation and de-allocation of entries
+ */
+static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh)
+{
+	if (__next_entry(lh) == NULL)
+		__next_entry(lh) = kmem_cache_alloc(tfrc_lh_slab, GFP_ATOMIC);
+
+	return __next_entry(lh);
+}
+
+void tfrc_lh_cleanup(struct tfrc_loss_hist *lh)
+{
+	if (tfrc_lh_is_initialised(lh))
+		for (lh->counter = 0; lh->counter < LIH_SIZE; lh->counter++)
+			if (__next_entry(lh) != NULL)
+				kmem_cache_free(tfrc_lh_slab, __next_entry(lh));
+}
+EXPORT_SYMBOL_GPL(tfrc_lh_cleanup);
+
 static struct kmem_cache *dccp_li_cachep __read_mostly;
 
 static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio)
@@ -98,6 +139,65 @@ u32 dccp_li_hist_calc_i_mean(struct list_head *list)
 
 EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean);
 
+static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh)
+{
+	u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
+	int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
+
+	for (i=0; i <= k; i++) {
+		i_i = tfrc_lh_get_interval(lh, i);
+
+		if (i < k) {
+			i_tot0 += i_i * tfrc_lh_weights[i];
+			w_tot  += tfrc_lh_weights[i];
+		}
+		if (i > 0)
+			i_tot1 += i_i * tfrc_lh_weights[i-1];
+	}
+
+	BUG_ON(w_tot == 0);
+	lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+}
+
+/**
+ * tfrc_lh_update_i_mean  -  Update the `open' loss interval I_0
+ * For recomputing p: returns `true' if p > p_prev  <=>  1/p < 1/p_prev
+ */
+u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb)
+{
+	struct tfrc_loss_interval *cur = tfrc_lh_peek(lh);
+	u32 old_i_mean = lh->i_mean;
+	s64 length;
+
+	if (cur == NULL)			/* not initialised */
+		return 0;
+
+	length = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq);
+
+	if (length - cur->li_length <= 0)	/* duplicate or reordered */
+		return 0;
+
+	if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4)
+		/*
+		 * Implements RFC 4342, 10.2:
+		 * If a packet S (skb) exists whose seqno comes `after' the one
+		 * starting the current loss interval (cur) and if the modulo-16
+		 * distance from C(cur) to C(S) is greater than 4, consider all
+		 * subsequent packets as belonging to a new loss interval. This
+		 * test is necessary since CCVal may wrap between intervals.
+		 */
+		cur->li_is_closed = 1;
+
+	if (tfrc_lh_length(lh) == 1)		/* due to RFC 3448, 6.3.1 */
+		return 0;
+
+	cur->li_length = length;
+	tfrc_lh_calc_i_mean(lh);
+
+	return (lh->i_mean < old_i_mean);
+}
+EXPORT_SYMBOL_GPL(tfrc_lh_update_i_mean);
+
 static int dccp_li_hist_interval_new(struct list_head *list,
 				     const u64 seq_loss, const u8 win_loss)
 {
@@ -284,6 +384,54 @@ void dccp_li_update_li(struct sock *sk,
 
 EXPORT_SYMBOL_GPL(dccp_li_update_li);
 
+/* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */
+static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur,
+				     struct tfrc_rx_hist_entry *new_loss)
+{
+	return	dccp_delta_seqno(cur->li_seqno, new_loss->tfrchrx_seqno) > 0 &&
+		(cur->li_is_closed || SUB16(new_loss->tfrchrx_ccval, cur->li_ccval) > 4);
+}
+
+/** tfrc_lh_interval_add  -  Insert new record into the Loss Interval database
+ * @lh:		   Loss Interval database
+ * @rh:		   Receive history containing a fresh loss event
+ * @calc_first_li: Caller-dependent routine to compute length of first interval
+ * @sk:		   Used by @calc_first_li in caller-specific way (subtyping)
+ * Updates I_mean and returns 1 if a new interval has in fact been added to @lh.
+ */
+int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh,
+			 u32 (*calc_first_li)(struct sock *), struct sock *sk)
+{
+	struct tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new;
+
+	if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh)))
+		return 0;
+
+	new = tfrc_lh_demand_next(lh);
+	if (unlikely(new == NULL)) {
+		DCCP_CRIT("Cannot allocate/add loss record.");
+		return 0;
+	}
+
+	new->li_seqno	  = tfrc_rx_hist_loss_prev(rh)->tfrchrx_seqno;
+	new->li_ccval	  = tfrc_rx_hist_loss_prev(rh)->tfrchrx_ccval;
+	new->li_is_closed = 0;
+
+	if (++lh->counter == 1)
+		lh->i_mean = new->li_length = (*calc_first_li)(sk);
+	else {
+		cur->li_length = dccp_delta_seqno(cur->li_seqno, new->li_seqno);
+		new->li_length = dccp_delta_seqno(new->li_seqno,
+				  tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno);
+		if (lh->counter > (2*LIH_SIZE))
+			lh->counter -= LIH_SIZE;
+
+		tfrc_lh_calc_i_mean(lh);
+	}
+	return 1;
+}
+EXPORT_SYMBOL_GPL(tfrc_lh_interval_add);
+
 int __init dccp_li_init(void)
 {
 	dccp_li_cachep = kmem_cache_create("dccp_li_hist",
diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h
index 27bee92..16d37fb 100644
--- a/net/dccp/ccids/lib/loss_interval.h
+++ b/net/dccp/ccids/lib/loss_interval.h
@@ -3,6 +3,7 @@
 /*
  *  net/dccp/ccids/lib/loss_interval.h
  *
+ *  Copyright (c) 2007   The University of Aberdeen, Scotland, UK
  *  Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
  *  Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
@@ -12,11 +13,66 @@
  *  Software Foundation; either version 2 of the License, or (at your option)
  *  any later version.
  */
-
 #include <linux/ktime.h>
 #include <linux/list.h>
+#include <linux/slab.h>
+
+/*
+ * Number of loss intervals (RFC 4342, 8.6.1). The history size is one more than
+ * NINTERVAL, since the `open' interval I_0 is always stored as the first entry.
+ * LIH_INDEX is used to implement LIFO semantics on the array.
+ */
+#define NINTERVAL	8
+#define LIH_SIZE	(NINTERVAL + 1)
+#define LIH_INDEX(ctr)	(LIH_SIZE - 1 - ((ctr) % LIH_SIZE))
+
+/**
+ *  tfrc_loss_interval  -  Loss history record for TFRC-based protocols
+ *  @li_seqno:		Highest received seqno before the start of loss
+ *  @li_ccval:		The CCVal belonging to @li_seqno
+ *  @li_is_closed:	Whether @li_seqno is older than 1 RTT
+ *  @li_length:		Loss interval sequence length
+ */
+struct tfrc_loss_interval {
+	u64		 li_seqno:48,
+			 li_ccval:4,
+			 li_is_closed:1;
+	u32		 li_length;
+};
+
+/**
+ *  tfrc_loss_hist  -  Loss record database
+ *  @ring:	Circular queue managed in LIFO manner
+ *  @counter:	Current count of entries (can be more than %LIH_SIZE)
+ *  @i_mean:	Current Average Loss Interval [RFC 3448, 5.4]
+ */
+struct tfrc_loss_hist {
+	struct tfrc_loss_interval	*ring[LIH_SIZE];
+	u8				counter;
+	u32				i_mean;
+};
+
+static inline void tfrc_lh_init(struct tfrc_loss_hist *lh)
+{
+	memset(lh, 0, sizeof(struct tfrc_loss_hist));
+}
+
+static inline u8 tfrc_lh_is_initialised(struct tfrc_loss_hist *lh)
+{
+	return lh->counter > 0;
+}
+
+static inline u8 tfrc_lh_length(struct tfrc_loss_hist *lh)
+{
+	return min(lh->counter, (u8)LIH_SIZE);
+}
 
 extern void dccp_li_hist_purge(struct list_head *list);
+struct tfrc_rx_hist;
+extern int  tfrc_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *,
+				 u32 (*first_li)(struct sock *), struct sock *);
+extern u8   tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *);
+extern void tfrc_lh_cleanup(struct tfrc_loss_hist *lh);
 
 extern u32 dccp_li_hist_calc_i_mean(struct list_head *list);
 
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index 428636e..a421032 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -214,6 +214,207 @@ int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h,
 }
 EXPORT_SYMBOL_GPL(tfrc_rx_hist_new_loss_indicated);
 
+static void tfrc_rx_hist_swap(struct tfrc_rx_hist_entry **a,
+			      struct tfrc_rx_hist_entry **b)
+{
+	struct tfrc_rx_hist_entry *tmp = *a;
+
+	*a = *b;
+	*b = tmp;
+}
+
+/*
+ * Private helper functions for loss detection.
+ *
+ * In the descriptions, `Si' refers to the sequence number of entry number i,
+ * whose NDP count is `Ni' (lower case is used for variables).
+ * Note: All __after_loss functions expect that a test against duplicates has
+ *       been performed already: the seqno of the skb must not be less than the
+ *       seqno of loss_prev; and it must not equal that of any valid hist_entry.
+ */
+static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2)
+{
+	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,
+	    s1 = TFRC_RX_HIST_ENTRY(h, 1)->tfrchrx_seqno,
+	    s2 = DCCP_SKB_CB(skb)->dccpd_seq;
+	int n1 = TFRC_RX_HIST_ENTRY(h, 1)->tfrchrx_ndp,
+	   d12 = dccp_delta_seqno(s1, s2), d2;
+
+	if (d12 > 0) {			/* S1  <  S2 */
+		h->loss_count = 2;
+		tfrc_rx_hist_entry_from_skb(TFRC_RX_HIST_ENTRY(h, 2), skb, n2);
+		return;
+	}
+
+	/* S0  <  S2  <  S1 */
+	d2 = dccp_delta_seqno(s0, s2);
+
+	if (d2 == 1 || n2 >= d2) {	/* S2 is direct successor of S0 */
+		int d21 = -d12;
+
+		if (d21 == 1 || n1 >= d21) {
+			/* hole is filled: S0, S2, and S1 are consecutive */
+			h->loss_count = 0;
+			h->loss_start = tfrc_rx_hist_index(h, 1);
+		} else
+			/* gap between S2 and S1: just update loss_prev */
+			tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2);
+
+	} else {			/* hole between S0 and S2 */
+		/*
+		 * Reorder history to insert S2 between S0 and s1
+		 */
+		tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 0), &TFRC_RX_HIST_ENTRY(h, 3));
+		h->loss_start = tfrc_rx_hist_index(h, 3);
+		tfrc_rx_hist_entry_from_skb(TFRC_RX_HIST_ENTRY(h, 1), skb, n2);
+		h->loss_count = 2;
+	}
+}
+
+/* return 1 if a new loss event has been identified */
+static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3)
+{
+	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,
+	    s1 = TFRC_RX_HIST_ENTRY(h, 1)->tfrchrx_seqno,
+	    s2 = TFRC_RX_HIST_ENTRY(h, 2)->tfrchrx_seqno,
+	    s3 = DCCP_SKB_CB(skb)->dccpd_seq;
+	int n1 = TFRC_RX_HIST_ENTRY(h, 1)->tfrchrx_ndp,
+	   d23 = dccp_delta_seqno(s2, s3), d13, d3, d31;
+
+	if (d23 > 0) {			/* S2  <  S3 */
+		h->loss_count = 3;
+		tfrc_rx_hist_entry_from_skb(TFRC_RX_HIST_ENTRY(h, 3), skb, n3);
+		return 1;
+	}
+
+	/* S3  <  S2 */
+	d13 = dccp_delta_seqno(s1, s3);
+
+	if (d13 > 0) {
+		/*
+		 * The sequence number order is S1, S3, S2
+		 * Reorder history to insert entry between S1 and S2
+		 */
+		tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 2), &TFRC_RX_HIST_ENTRY(h, 3));
+		tfrc_rx_hist_entry_from_skb(TFRC_RX_HIST_ENTRY(h, 2), skb, n3);
+		h->loss_count = 3;
+		return 1;
+	}
+
+	/* S0  <  S3  <  S1 */
+	d31 = -d13;
+	d3  = dccp_delta_seqno(s0, s3);
+
+	if (d3 == 1 || n3 >= d3) {	/* S3 is a successor of S0 */
+
+		if (d31 == 1 || n1 >= d31) {
+			/* hole between S0 and S1 filled by S3 */
+			int  d2 = dccp_delta_seqno(s1, s2),
+			     n2 = TFRC_RX_HIST_ENTRY(h, 2)->tfrchrx_ndp;
+
+			if (d2 == 1 || n2 >= d2) {
+				/* entire hole filled by S0, S3, S1, S2 */
+				h->loss_start = tfrc_rx_hist_index(h, 2);
+				h->loss_count = 0;
+			} else {
+				/* gap remains between S1 and S2 */
+				h->loss_start = tfrc_rx_hist_index(h, 1);
+				h->loss_count = 1;
+			}
+
+		} else /* gap exists between S3 and S1, loss_count stays at 2 */
+			tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n3);
+
+		return 0;
+	}
+
+	/*
+	 * The remaining case: S3 is not a successor of S0.
+	 * Sequence order is S0, S3, S1, S2; reorder to insert between S0 and S1
+	 */
+	tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 0), &TFRC_RX_HIST_ENTRY(h, 3));
+	h->loss_start = tfrc_rx_hist_index(h, 3);
+	tfrc_rx_hist_entry_from_skb(TFRC_RX_HIST_ENTRY(h, 1), skb, n3);
+	h->loss_count = 3;
+
+	return 1;
+}
+
+/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */
+static s64 tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist *h, u8 e1, u8 e2)
+{
+	DCCP_BUG_ON(e1 > h->loss_count || e2 > h->loss_count);
+
+	return dccp_delta_seqno(TFRC_RX_HIST_ENTRY(h, e1)->tfrchrx_seqno,
+				TFRC_RX_HIST_ENTRY(h, e2)->tfrchrx_seqno);
+}
+
+/* recycle RX history records to continue loss detection if necessary */
+static void __three_after_loss(struct tfrc_rx_hist *h)
+{
+	/*
+	 * The distance between S0 and S1 is always greater than 1 and the NDP
+	 * count of S1 is smaller than this distance. Otherwise there would
+	 * have been no loss. Hence it is only necessary to see whether there
+	 * are further missing data packets between S1/S2 and S2/S3.
+	 */
+	int d2 = tfrc_rx_hist_delta_seqno(h, 1, 2),
+	    d3 = tfrc_rx_hist_delta_seqno(h, 2, 3),
+	    n2 = TFRC_RX_HIST_ENTRY(h, 2)->tfrchrx_ndp,
+	    n3 = TFRC_RX_HIST_ENTRY(h, 3)->tfrchrx_ndp;
+
+	if (d2 == 1 || n2 >= d2) {	/* S2 is successor to S1 */
+
+		if (d3 == 1 || n3 >= d3) {
+			/* S3 is successor of S2: entire hole is filled */
+			h->loss_start = tfrc_rx_hist_index(h, 3);
+			h->loss_count = 0;
+		} else {
+			/* gap between S2 and S3 */
+			h->loss_start = tfrc_rx_hist_index(h, 2);
+			h->loss_count = 1;
+		}
+
+	} else {			/* gap between S1 and S2 */
+		h->loss_start = tfrc_rx_hist_index(h, 1);
+		h->loss_count = 2;
+	}
+}
+
+/**
+ *  tfrc_rx_handle_loss  -  Loss detection and further processing
+ *  @h:		    The non-empty RX history object
+ *  @lh:	    Loss Intervals database to update
+ *  @skb:	    Currently received packet
+ *  @ndp:	    The NDP count belonging to @skb
+ *  @calc_first_li: Caller-dependent computation of first loss interval in @lh
+ *  @sk:	    Used by @calc_first_li (see tfrc_lh_interval_add)
+ *  Chooses action according to pending loss, updates LI database when a new
+ *  loss was detected, and does required post-processing. Returns 1 when caller
+ *  should send feedback, 0 otherwise.
+ */
+int tfrc_rx_handle_loss(struct tfrc_rx_hist *h,
+			struct tfrc_loss_hist *lh,
+			struct sk_buff *skb, u32 ndp,
+			u32 (*calc_first_li)(struct sock *), struct sock *sk)
+{
+	int is_new_loss = 0;
+
+	if (h->loss_count == 1) {
+		__one_after_loss(h, skb, ndp);
+	} else if (h->loss_count != 2) {
+		DCCP_BUG("invalid loss_count %d", h->loss_count);
+	} else if (__two_after_loss(h, skb, ndp)) {
+		/*
+		 * Update Loss Interval database and recycle RX records
+		 */
+		is_new_loss = tfrc_lh_interval_add(lh, h, calc_first_li, sk);
+		__three_after_loss(h);
+	}
+	return is_new_loss;
+}
+EXPORT_SYMBOL_GPL(tfrc_rx_handle_loss);
+
 int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h)
 {
 	int i;
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index 6ea25cd..6df9582 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -36,10 +36,9 @@
 #ifndef _DCCP_PKT_HIST_
 #define _DCCP_PKT_HIST_
 
-#include <linux/ktime.h>
-#include <linux/types.h>
-
-struct sk_buff;
+#include <linux/list.h>
+#include <linux/slab.h>
+#include "tfrc.h"
 
 struct tfrc_tx_hist_entry;
 
@@ -122,6 +121,10 @@ extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 extern int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb);
 extern int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h,
 					   const struct sk_buff *skb, u32 ndp);
+struct tfrc_loss_hist;
+extern int  tfrc_rx_handle_loss(struct tfrc_rx_hist *, struct tfrc_loss_hist *,
+				struct sk_buff *skb, u32 ndp,
+				u32 (*first_li)(struct sock *), struct sock *);
 extern u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h,
 				   const struct sk_buff *skb);
 extern int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h);
diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h
index ab8848c..1fb1187 100644
--- a/net/dccp/ccids/lib/tfrc.h
+++ b/net/dccp/ccids/lib/tfrc.h
@@ -17,6 +17,9 @@
 #include <linux/types.h>
 #include <asm/div64.h>
 #include "../../dccp.h"
+/* internal includes that this module exports: */
+#include "loss_interval.h"
+#include "packet_history.h"
 
 #ifdef CONFIG_IP_DCCP_TFRC_DEBUG
 extern int tfrc_debug;

[PATCH 7/8] [TFRC]: CCID3 (and CCID4) needs to access these inlines

[Gerrit Renker]

This moves two inlines back to packet_history.h: these are not private
to packet_history.c, but are needed by CCID3/4 to detect whether a new
loss is indicated, or whether a loss is already pending.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/packet_history.c |   26 --------------------------
 net/dccp/ccids/lib/packet_history.h |   28 ++++++++++++++++++++++++++--
 2 files changed, 26 insertions(+), 28 deletions(-)

diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index a421032..760631e 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -188,32 +188,6 @@ void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 }
 EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet);
 
-/* initialise loss detection and disable RTT sampling */
-static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h)
-{
-	h->loss_count = 1;
-}
-
-/* indicate whether previously a packet was detected missing */
-static inline int tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist *h)
-{
-	return h->loss_count;
-}
-
-/* any data packets missing between last reception and skb ? */
-int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h,
-				    const struct sk_buff *skb, u32 ndp)
-{
-	int delta = dccp_delta_seqno(tfrc_rx_hist_last_rcv(h)->tfrchrx_seqno,
-				     DCCP_SKB_CB(skb)->dccpd_seq);
-
-	if (delta > 1 && ndp < delta)
-		tfrc_rx_hist_loss_indicated(h);
-
-	return tfrc_rx_hist_loss_pending(h);
-}
-EXPORT_SYMBOL_GPL(tfrc_rx_hist_new_loss_indicated);
-
 static void tfrc_rx_hist_swap(struct tfrc_rx_hist_entry **a,
 			      struct tfrc_rx_hist_entry **b)
 {
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index 6df9582..cb3220f 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -115,12 +115,36 @@ static inline struct tfrc_rx_hist_entry *
 	return h->ring[h->loss_start];
 }
 
+/* initialise loss detection and disable RTT sampling */
+static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h)
+{
+	h->loss_count = 1;
+}
+
+/* indicate whether previously a packet was detected missing */
+static inline int tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist *h)
+{
+	return h->loss_count;
+}
+
+/* any data packets missing between last reception and skb ? */
+static inline int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h,
+						  const struct sk_buff *skb, u32 ndp)
+{
+	int delta = dccp_delta_seqno(tfrc_rx_hist_last_rcv(h)->tfrchrx_seqno,
+				     DCCP_SKB_CB(skb)->dccpd_seq);
+
+	if (delta > 1 && ndp < delta)
+		tfrc_rx_hist_loss_indicated(h);
+
+	return tfrc_rx_hist_loss_pending(h);
+}
+
 extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
 				    const struct sk_buff *skb, const u32 ndp);
 
 extern int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb);
-extern int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h,
-					   const struct sk_buff *skb, u32 ndp);
+
 struct tfrc_loss_hist;
 extern int  tfrc_rx_handle_loss(struct tfrc_rx_hist *, struct tfrc_loss_hist *,
 				struct sk_buff *skb, u32 ndp,

[PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Gerrit Renker]

This hooks up the TFRC Loss Interval database with CCID 3 packet reception.
In addition, it makes the CCID-specific computation of the first loss
interval (which requires access to all the guts of CCID3) local to ccid3.c.

The patch also fixes an omission in the DCCP code, that of a default /
fallback RTT value (defined in section 3.4 of RFC 4340 as 0.2 sec); while
at it, the  upper bound of 4 seconds for an RTT sample has  been reduced to
match the initial TCP RTO value of 3 seconds from[RFC 1122, 4.2.3.1].

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
---
 net/dccp/ccids/ccid3.c |   72 ++++++++++++++++++++++++++++++++++++++++--------
 net/dccp/ccids/ccid3.h |   10 +++---
 net/dccp/dccp.h        |    7 +++-
 3 files changed, 70 insertions(+), 19 deletions(-)

diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
index 60fcb31..4d0de21 100644
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -1,6 +1,7 @@
 /*
  *  net/dccp/ccids/ccid3.c
  *
+ *  Copyright (c) 2007   The University of Aberdeen, Scotland, UK
  *  Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
  *  Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
  *
@@ -33,11 +34,7 @@
  *  along with this program; if not, write to the Free Software
  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
-#include "../ccid.h"
 #include "../dccp.h"
-#include "lib/packet_history.h"
-#include "lib/loss_interval.h"
-#include "lib/tfrc.h"
 #include "ccid3.h"
 
 #include <asm/unaligned.h>
@@ -759,6 +756,46 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
 	return 0;
 }
 
+/** ccid3_first_li  -  Implements [RFC 3448, 6.3.1]
+ *
+ * Determine the length of the first loss interval via inverse lookup.
+ * Assume that X_recv can be computed by the throughput equation
+ *		    s
+ *	X_recv = --------
+ *		 R * fval
+ * Find some p such that f(p) = fval; return 1/p (scaled).
+ */
+static u32 ccid3_first_li(struct sock *sk)
+{
+	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
+	u32 x_recv, p, delta;
+	u64 fval;
+
+	if (hcrx->ccid3hcrx_rtt == 0) {
+		DCCP_WARN("No RTT estimate available, using fallback RTT\n");
+		hcrx->ccid3hcrx_rtt = DCCP_FALLBACK_RTT;
+	}
+
+	delta = ktime_to_us(net_timedelta(hcrx->ccid3hcrx_tstamp_last_feedback));
+	x_recv = scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta);
+	if (x_recv == 0) {		/* would also trigger divide-by-zero */
+		DCCP_WARN("X_recv==0\n");
+		if ((x_recv = hcrx->ccid3hcrx_x_recv) == 0) {
+			DCCP_BUG("stored value of X_recv is zero");
+			return ~0U;
+		}
+	}
+
+	fval = scaled_div(hcrx->ccid3hcrx_s, hcrx->ccid3hcrx_rtt);
+	fval = scaled_div32(fval, x_recv);
+	p = tfrc_calc_x_reverse_lookup(fval);
+
+	ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
+		       "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
+
+	return p == 0 ? ~0U : scaled_div(1, p);
+}
+
 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 {
 	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
@@ -796,6 +833,14 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 	/*
 	 * Handle pending losses and otherwise check for new loss
 	 */
+	if (tfrc_rx_hist_loss_pending(&hcrx->ccid3hcrx_hist) &&
+	    tfrc_rx_handle_loss(&hcrx->ccid3hcrx_hist,
+				&hcrx->ccid3hcrx_li_hist,
+				skb, ndp, ccid3_first_li, sk) ) {
+		do_feedback = CCID3_FBACK_PARAM_CHANGE;
+		goto done_receiving;
+	}
+
 	if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp))
 		goto update_records;
 
@@ -805,7 +850,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 	if (unlikely(!is_data_packet))
 		goto update_records;
 
-	if (list_empty(&hcrx->ccid3hcrx_li_hist)) {  /* no loss so far: p = 0 */
+	if (!tfrc_lh_is_initialised(&hcrx->ccid3hcrx_li_hist)) {
 		const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_hist, skb);
 		/*
 		 * Empty loss history: no loss so far, hence p stays 0.
@@ -814,6 +859,13 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 		 */
 		if (sample != 0)
 			hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9);
+
+	} else if (tfrc_lh_update_i_mean(&hcrx->ccid3hcrx_li_hist, skb)) {
+		/*
+		 * Step (3) of [RFC 3448, 6.1]: Recompute I_mean and, if I_mean
+		 * has decreased (resp. p has increased), send feedback now.
+		 */
+		do_feedback = CCID3_FBACK_PARAM_CHANGE;
 	}
 
 	/*
@@ -825,6 +877,7 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 update_records:
 	tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);
 
+done_receiving:
 	if (do_feedback)
 		ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
 }
@@ -833,10 +886,8 @@ static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk)
 {
 	struct ccid3_hc_rx_sock *hcrx = ccid_priv(ccid);
 
-	ccid3_pr_debug("entry\n");
-
 	hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
-	INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist);
+	tfrc_lh_init(&hcrx->ccid3hcrx_li_hist);
 	return tfrc_rx_hist_alloc(&hcrx->ccid3hcrx_hist);
 }
 
@@ -846,11 +897,8 @@ static void ccid3_hc_rx_exit(struct sock *sk)
 
 	ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
 
-	/* Empty packet history */
 	tfrc_rx_hist_purge(&hcrx->ccid3hcrx_hist);
-
-	/* Empty loss interval history */
-	dccp_li_hist_purge(&hcrx->ccid3hcrx_li_hist);
+	tfrc_lh_cleanup(&hcrx->ccid3hcrx_li_hist);
 }
 
 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h
index 3c33dc6..2dede8e 100644
--- a/net/dccp/ccids/ccid3.h
+++ b/net/dccp/ccids/ccid3.h
@@ -41,7 +41,7 @@
 #include <linux/list.h>
 #include <linux/types.h>
 #include <linux/tfrc.h>
-#include "lib/packet_history.h"
+#include "lib/tfrc.h"
 #include "../ccid.h"
 
 /* Two seconds as per RFC 3448 4.2 */
@@ -141,8 +141,8 @@ enum ccid3_hc_rx_states {
  *  @ccid3hcrx_bytes_recv  -  Total sum of DCCP payload bytes
  *  @ccid3hcrx_tstamp_last_feedback  -  Time at which last feedback was sent
  *  @ccid3hcrx_tstamp_last_ack  -  Time at which last feedback was sent
- *  @ccid3hcrx_hist  -  Packet history
- *  @ccid3hcrx_li_hist  -  Loss Interval History
+ *  @ccid3hcrx_hist  -  Packet history (loss detection + RTT sampling)
+ *  @ccid3hcrx_li_hist  -  Loss Interval database
  *  @ccid3hcrx_s  -  Received packet size in bytes
  *  @ccid3hcrx_pinv  -  Inverse of Loss Event Rate (RFC 4342, sec. 8.5)
  */
@@ -156,9 +156,9 @@ struct ccid3_hc_rx_sock {
 	u32				ccid3hcrx_bytes_recv;
 	ktime_t				ccid3hcrx_tstamp_last_feedback;
 	struct tfrc_rx_hist		ccid3hcrx_hist;
-	struct list_head		ccid3hcrx_li_hist;
+	struct tfrc_loss_hist		ccid3hcrx_li_hist;
 	u16				ccid3hcrx_s;
-	u32				ccid3hcrx_pinv;
+#define ccid3hcrx_pinv			ccid3hcrx_li_hist.i_mean
 };
 
 static inline struct ccid3_hc_rx_sock *ccid3_hc_rx_sk(const struct sock *sk)
diff --git a/net/dccp/dccp.h b/net/dccp/dccp.h
index f4a5ea1..07dcbe7 100644
--- a/net/dccp/dccp.h
+++ b/net/dccp/dccp.h
@@ -74,9 +74,12 @@ extern void dccp_time_wait(struct sock *sk, int state, int timeo);
 
 #define DCCP_RTO_MAX ((unsigned)(120 * HZ)) /* FIXME: using TCP value */
 
-/* bounds for sampled RTT values from packet exchanges (in usec) */
+/*
+ * RTT sampling: sanity bounds and fallback RTT value from RFC 4340, section 3.4
+ */
 #define DCCP_SANE_RTT_MIN	100
-#define DCCP_SANE_RTT_MAX	(4 * USEC_PER_SEC)
+#define DCCP_FALLBACK_RTT	(USEC_PER_SEC / 5)
+#define DCCP_SANE_RTT_MAX	(3 * USEC_PER_SEC)
 
 /* Maximal interval between probes for local resources.  */
 #define DCCP_RESOURCE_PROBE_INTERVAL ((unsigned)(HZ / 2U))

Re: [PATCH 1/8] [TFRC]: Whitespace cleanups

[Arnaldo Carvalho de Melo]

Em Sat, Dec 08, 2007 at 10:06:21AM +0000, Gerrit Renker escreveu:
> Just some tidy-ups to keep git/quilt happy. Also moved up the
> comment "Receiver routines" above the first occurrence of RX
> history routines.
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>

Thanks, applied.

Re: [PATCH 2/8] [TFRC]: Put RX/TX initialisation into tfrc.c

[Arnaldo Carvalho de Melo]

Em Sat, Dec 08, 2007 at 10:06:22AM +0000, Gerrit Renker escreveu:
> This separates RX/TX initialisation and puts all packet history / loss intervals
> initialisation into tfrc.c.
> The organisation is uniform: slab declaration -> {rx,tx}_init() -> {rx,tx}_exit()

NAK, you can't call a __exit marked routine from a __init marked
routine.

- Arnaldo
 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
> ---
>  net/dccp/ccids/lib/packet_history.c |   68 ++++++++++++++++------------------
>  net/dccp/ccids/lib/tfrc.c           |   31 ++++++++++++----
>  2 files changed, 55 insertions(+), 44 deletions(-)
> 
> diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
> index 54cd23e..af0db71 100644
> --- a/net/dccp/ccids/lib/packet_history.c
> +++ b/net/dccp/ccids/lib/packet_history.c
> @@ -57,6 +57,22 @@ struct tfrc_tx_hist_entry {
>   */

<SNIP>

> +
> +void __exit tfrc_tx_packet_history_exit(void)
> +{
> +	if (tfrc_tx_hist_slab != NULL) {
> +		kmem_cache_destroy(tfrc_tx_hist_slab);
> +		tfrc_tx_hist_slab = NULL;
> +	}
> +}
> +

<SNIP>

> diff --git a/net/dccp/ccids/lib/tfrc.c b/net/dccp/ccids/lib/tfrc.c
> index 3a7a183..20763fa 100644
> --- a/net/dccp/ccids/lib/tfrc.c
> +++ b/net/dccp/ccids/lib/tfrc.c
> @@ -14,27 +14,42 @@ module_param(tfrc_debug, bool, 0444);
>  MODULE_PARM_DESC(tfrc_debug, "Enable debug messages");
>  #endif
>  
> +extern int  tfrc_tx_packet_history_init(void);
> +extern void tfrc_tx_packet_history_exit(void);
> +extern int  tfrc_rx_packet_history_init(void);
> +extern void tfrc_rx_packet_history_exit(void);
> +
>  extern int  dccp_li_init(void);
>  extern void dccp_li_exit(void);
> -extern int packet_history_init(void);
> -extern void packet_history_exit(void);
>  
>  static int __init tfrc_module_init(void)
>  {
>  	int rc = dccp_li_init();
>  
> -	if (rc == 0) {
> -		rc = packet_history_init();
> -		if (rc != 0)
> -			dccp_li_exit();
> -	}
> +	if (rc)
> +		goto out;
> +
> +	rc = tfrc_tx_packet_history_init();
> +	if (rc)
> +		goto out_free_loss_intervals;
>  
> +	rc = tfrc_rx_packet_history_init();
> +	if (rc)
> +		goto out_free_tx_history;
> +	return 0;
> +
> +out_free_tx_history:
> +	tfrc_tx_packet_history_exit();
> +out_free_loss_intervals:
> +	dccp_li_exit();
> +out:
>  	return rc;
>  }

<SNIP>

Re: [PATCH 3/8] [TFRC/CCID3]: Remove now unused functions / function calls

[Arnaldo Carvalho de Melo]

Em Sat, Dec 08, 2007 at 10:06:23AM +0000, Gerrit Renker escreveu:
> This removes two things which now have become redundant:
>  1. The function tfrc_rx_hist_entry_delete() is no longer referenced anywhere.
>  2. The CCID3 HC-receiver still inserted timestamps, but received timestamps
>     are not parsed/referenced/used by the HC-sender, it serves no function.
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>

Thanks, applying as two separate patches.

- Arnaldo

Re: [PATCH 5/8] [TFRC]: Loss interval code needs the macros/inlines that were moved

[Arnaldo Carvalho de Melo]

Em Sat, Dec 08, 2007 at 10:06:25AM +0000, Gerrit Renker escreveu:
> This moves the inlines (which were previously declared as macros) back into packet_history.h since
> the loss detection code needs to be able to read entries from the RX history in order to create the
> relevant loss entries: it needs at least tfrc_rx_hist_loss_prev() and tfrc_rx_hist_last_rcv(), which
> in turn require the definition of the other inlines (macros).
> 
> Additionally, inn one case the use of inlines instead of a macro broke the algorithm: rx_hist_swap()
> (introduced in next patch) needs to be able to swap the history entries; when using an inline returning
> a pointer instead, one gets compilation errors such as:
> 
>   distcc[24516] ERROR: compile /root/.ccache/packet_his.tmp.aspire.home.net.24512.i on _tiptop failed
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__one_after_loss':
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:266: error: lvalue required as unary '&' operand
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:267: error: lvalue required as unary '&' operand
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__two_after_loss':
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:298: error: lvalue required as unary '&' operand
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:299: error: lvalue required as unary '&' operand
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:336: error: lvalue required as unary '&' operand
>   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:337: error: lvalue required as unary '&' operand
>   make[4]: *** [net/dccp/ccids/lib/packet_history.o] Error 1
>   make[3]: *** [net/dccp/ccids/lib] Error 2
>   make[2]: *** [net/dccp/ccids] Error 2
>   make[1]: *** [net/dccp/] Error 2
>   make: *** [sub-make] Error 2

Because you do it this way:

tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 0), &TFRC_RX_HIST_ENTRY(h, 3));

I checked and at least in this patch series all uses are of this type,
so why not do it using just the indexes, which would be simpler:

tfrc_rx_hist_swap(h, 0, 3);

With this implementation:

static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const int a, const int b)
{
	const int idx_a = tfrc_rx_hist_index(h, a),
	      int idx_b = tfrc_rx_hist_index(h, b);
	struct tfrc_rx_hist_entry *tmp = h->ring[idx_a];

	h->ring[idx_a] = h->ring[idx_b];
	h->ring[idx_b] = tmp;
}

- Arnaldo

Re: [PATCH 2/8] [TFRC]: Put RX/TX initialisation into tfrc.c

[Gerrit Renker]

| > This separates RX/TX initialisation and puts all packet history / loss intervals
| > initialisation into tfrc.c.
| > The organisation is uniform: slab declaration -> {rx,tx}_init() -> {rx,tx}_exit()
| 
| NAK, you can't call a __exit marked routine from a __init marked
| routine.
| 
Ok thanks, will fix that in revision 2.

Re: [PATCH 5/8] [TFRC]: Loss interval code needs the macros/inlines that were moved

[Gerrit Renker]

| > 
| >   distcc[24516] ERROR: compile /root/.ccache/packet_his.tmp.aspire.home.net.24512.i on _tiptop failed
| >   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__one_after_loss':
| >   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:266: error: lvalue required as unary '&' operand
<snip>
| 
| Because you do it this way:
| 
| tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 0), &TFRC_RX_HIST_ENTRY(h, 3));
| 
| I checked and at least in this patch series all uses are of this type,
| so why not do it using just the indexes, which would be simpler:
| 
| tfrc_rx_hist_swap(h, 0, 3);
| 
| With this implementation:
| 
| static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const int a, const int b)
| {
| 	const int idx_a = tfrc_rx_hist_index(h, a),
| 	      int idx_b = tfrc_rx_hist_index(h, b);
| 	struct tfrc_rx_hist_entry *tmp = h->ring[idx_a];
| 
| 	h->ring[idx_a] = h->ring[idx_b];
| 	h->ring[idx_b] = tmp;
| }
| 
Agreed, that is useful in the present case, since then everything uses
inlines. The only suggestion I'd like to make is to use `u8' instead of 
`int' since the indices will have very low values.

There is a related point: you will probably have noticed that loss_interval.c 
also uses macros. I don't know if you are planning to convert these also into 
inlines. I think that there would be less benefit in converting these, since
they are locl to loss_interval.c and mostly serve to improve readability.

As I have at least one other patch to revise (plus another minor one),
I'll rework this according to the above. 

Re: [PATCH 5/8] [TFRC]: Loss interval code needs the macros/inlines that were moved

[Arnaldo Carvalho de Melo]

Em Mon, Dec 10, 2007 at 11:31:53AM +0000, Gerrit Renker escreveu:
> | > 
> | >   distcc[24516] ERROR: compile /root/.ccache/packet_his.tmp.aspire.home.net.24512.i on _tiptop failed
> | >   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c: In function '__one_after_loss':
> | >   /usr/src/davem-2.6/net/dccp/ccids/lib/packet_history.c:266: error: lvalue required as unary '&' operand
> <snip>
> | 
> | Because you do it this way:
> | 
> | tfrc_rx_hist_swap(&TFRC_RX_HIST_ENTRY(h, 0), &TFRC_RX_HIST_ENTRY(h, 3));
> | 
> | I checked and at least in this patch series all uses are of this type,
> | so why not do it using just the indexes, which would be simpler:
> | 
> | tfrc_rx_hist_swap(h, 0, 3);
> | 
> | With this implementation:
> | 
> | static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const int a, const int b)
> | {
> | 	const int idx_a = tfrc_rx_hist_index(h, a),
> | 	      int idx_b = tfrc_rx_hist_index(h, b);
> | 	struct tfrc_rx_hist_entry *tmp = h->ring[idx_a];
> | 
> | 	h->ring[idx_a] = h->ring[idx_b];
> | 	h->ring[idx_b] = tmp;
> | }
> | 
> Agreed, that is useful in the present case, since then everything uses
> inlines. The only suggestion I'd like to make is to use `u8' instead of 
> `int' since the indices will have very low values.

Agreed.
 
> There is a related point: you will probably have noticed that loss_interval.c 
> also uses macros. I don't know if you are planning to convert these also into 
> inlines. I think that there would be less benefit in converting these, since
> they are locl to loss_interval.c and mostly serve to improve readability.

In general I'm against using macros for functions, so please always
consider doing things as inlines.

I'll read some more patches today and provide comments as to if I think
it is ok for now to keep it as macros.

> As I have at least one other patch to revise (plus another minor one),
> I'll rework this according to the above. 

Thank you.

- Arnaldo

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Arnaldo Carvalho de Melo]

Em Sat, Dec 08, 2007 at 10:06:28AM +0000, Gerrit Renker escreveu:
> This hooks up the TFRC Loss Interval database with CCID 3 packet reception.
> In addition, it makes the CCID-specific computation of the first loss
> interval (which requires access to all the guts of CCID3) local to ccid3.c.
> 
> The patch also fixes an omission in the DCCP code, that of a default /
> fallback RTT value (defined in section 3.4 of RFC 4340 as 0.2 sec); while
> at it, the  upper bound of 4 seconds for an RTT sample has  been reduced to
> match the initial TCP RTO value of 3 seconds from[RFC 1122, 4.2.3.1].
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
> Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>

When interfacing we must make sure that ccid3 tfrc_lh_slab is created
and then tfrc_li_cachep is not needed. I'm doing this while keeping
the structure of the patches, i.e. one introducing, the other removing.
But we need to create tfrc_lh_slab if we want the tree to be bisectable.

I'm doing this and keeping your Signed-off-line, please holler if you
disagree for some reason.

- Arnaldo

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Gerrit Renker]

| When interfacing we must make sure that ccid3 tfrc_lh_slab is created
| and then tfrc_li_cachep is not needed. I'm doing this while keeping
| the structure of the patches, i.e. one introducing, the other removing.
| But we need to create tfrc_lh_slab if we want the tree to be bisectable.
| 
| I'm doing this and keeping your Signed-off-line, please holler if you
| disagree for some reason.
If you are just shifting and reordering then that is fine with me. But
it seems you mean a different patch since in this one there is no slab
initialisation. 
The loss history and the RX/TX packet history slabs are all created in
tfrc.c using the three different __init routines of the dccp_tfrc_lib.

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Arnaldo Carvalho de Melo]

Em Tue, Dec 11, 2007 at 09:42:38AM +0000, Gerrit Renker escreveu:
> | When interfacing we must make sure that ccid3 tfrc_lh_slab is created
> | and then tfrc_li_cachep is not needed. I'm doing this while keeping
> | the structure of the patches, i.e. one introducing, the other removing.
> | But we need to create tfrc_lh_slab if we want the tree to be bisectable.
> | 
> | I'm doing this and keeping your Signed-off-line, please holler if you
> | disagree for some reason.
> If you are just shifting and reordering then that is fine with me. But
> it seems you mean a different patch since in this one there is no slab
> initialisation. 

This time around I'm not doing any reordering, just trying to use your
patches as is, but adding this patch as-is produces a kernel that will
crash, no?

> The loss history and the RX/TX packet history slabs are all created in
> tfrc.c using the three different __init routines of the dccp_tfrc_lib.

Yes, the init routines are called and in turn they create the slab
caches, but up to the patch "[PATCH 8/8] [PATCH v2] [CCID3]: Interface
CCID3 code with newer Loss Intervals Database" the new li slab is not
being created, no? See what I'm talking?

- Arnaldo

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Gerrit Renker]

| This time around I'm not doing any reordering, just trying to use your
| patches as is, but adding this patch as-is produces a kernel that will
| crash, no?
| 
| > The loss history and the RX/TX packet history slabs are all created in
| > tfrc.c using the three different __init routines of the dccp_tfrc_lib.
| 
| Yes, the init routines are called and in turn they create the slab
| caches, but up to the patch "[PATCH 8/8] [PATCH v2] [CCID3]: Interface
| CCID3 code with newer Loss Intervals Database" the new li slab is not
| being created, no? See what I'm talking?
| 
Sorry, there is some weird kind of mix-up going on. Can you please check
your patch set: it seems this email exchange refers to an older variant.
In the most recent patch set, the slab is introduced in the patch

	[TFRC]: Ringbuffer to track loss interval history

--- a/net/dccp/ccids/lib/loss_interval.c
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -27,6 +23,54 @@ struct dccp_li_hist_entry {
        u32              dccplih_interval;
 };

+static struct kmem_cache  *tfrc_lh_slab  __read_mostly;	/* <=== */
+/* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */
+static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 };
// ...

And this is 6/8, i.e. before 8/8, cf.
	http://www.mail-archive.com/dccp@vger.kernel.org/msg03000.html
     
I don't know which tree you are working off, would it be possible to
check against the test tree
	git://eden-feed.erg.abdn.ac.uk/dccp_exp		[dccp]

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Arnaldo Carvalho de Melo]

Em Wed, Dec 12, 2007 at 04:56:32PM +0000, Gerrit Renker escreveu:
> | This time around I'm not doing any reordering, just trying to use your
> | patches as is, but adding this patch as-is produces a kernel that will
> | crash, no?
> | 
> | > The loss history and the RX/TX packet history slabs are all created in
> | > tfrc.c using the three different __init routines of the dccp_tfrc_lib.
> | 
> | Yes, the init routines are called and in turn they create the slab
> | caches, but up to the patch "[PATCH 8/8] [PATCH v2] [CCID3]: Interface
> | CCID3 code with newer Loss Intervals Database" the new li slab is not
> | being created, no? See what I'm talking?
> | 
> Sorry, there is some weird kind of mix-up going on. Can you please check
> your patch set: it seems this email exchange refers to an older variant.
> In the most recent patch set, the slab is introduced in the patch
> 
> 	[TFRC]: Ringbuffer to track loss interval history
> 
> --- a/net/dccp/ccids/lib/loss_interval.c
> +++ b/net/dccp/ccids/lib/loss_interval.c
> @@ -27,6 +23,54 @@ struct dccp_li_hist_entry {
>         u32              dccplih_interval;
>  };
> 
> +static struct kmem_cache  *tfrc_lh_slab  __read_mostly;	/* <=== */

Yup, this one, is introduced as above but is not initialized at the
module init routine, please see, it should be OK and we can move on:

http://git.kernel.org/?p=linux/kernel/git/acme/net-2.6.25.git;a=commitdiff;h=a925429ce2189b548dc19037d3ebd4ff35ae4af7

> +/* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */
> +static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 };
> // ...
> 
> And this is 6/8, i.e. before 8/8, cf.
> 	http://www.mail-archive.com/dccp@vger.kernel.org/msg03000.html
>      
> I don't know which tree you are working off, would it be possible to
> check against the test tree
> 	git://eden-feed.erg.abdn.ac.uk/dccp_exp		[dccp]

I'm doing a fresh clone now. But I think that everything is OK after
today's merge request I sent to David.

- Arnaldo

Re: [PATCH 8/8] [PATCH v2] [CCID3]: Interface CCID3 code with newer Loss Intervals Database

[Gerrit Renker]

| > +static struct kmem_cache  *tfrc_lh_slab  __read_mostly;	/* <=== */
| 
| Yup, this one, is introduced as above but is not initialized at the
| module init routine, please see, it should be OK and we can move on:
| 
| http://git.kernel.org/?p=linux/kernel/git/acme/net-2.6.25.git;a=commitdiff;h=a925429ce2189b548dc19037d3ebd4ff35ae4af7
| 
Sorry for the confusion - you were right, the initialisation was sitting
in the wrong patch, not the one in the subject line. In your online
version the problem is fixed. Thanks a lot for all the work and for the
clarification.

Gerrit