[PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

Orthogonal to the ongoing discussion of patches, here are updates
of existing ones. This is mainly to keep the test tree in synch;
I'd like to upload the new test tree since -rc4 is out.

Arnaldo has actually pointed out more bugs than I have given him credit for,
these are contained in this patch set.

Patch #1: Fixes the allocation of per-socket RX history array elements
          (implements the solution contributed by Arnaldo).

Patch #2: Fixes a similar problem in the tfrc_module.c -- this solution
          is also present in Arnaldo's patch set, but he did not explicitly
	  point it out. The update fixes this problem (it used to disappear
	  later in the patch set, when the full initialisation was made for
	  TX/RX histories and Loss Intervals; so it is only temporary).

Patch #3: Removes the redundant test "len > 0", as a result one inline function
          becomes obsolete. Thanks is again due to Arnaldo.

I have not yet updated the CCID4 subtree with regard to patch#3 but will do
as soon as work here permits.

The updates to the tree are now available at
 	git://eden-feed.erg.abdn.ac.uk/dccp_exp		{dccp,ccid4} 

[PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

This revision fixes a bug present in the per-socket allocation of RX history 
entries; identification of this bug is thanks to Arnaldo Carvalho de Melo.

The bug was in not deallocating history entries when the allocation of 
one array element failed. The solution in this revised patch set is the
original one written by Arnaldo.

----------------------> Patch v2 <---------------------------------------------
[TFRC]: New RX history implementation

This provides a new, self-contained and generic RX history service for TFRC
based protocols.

Details:
 * new data structure, initialisation and cleanup routines;
 * allocation of dccp_rx_hist entries local to packet_history.c, 
   as a service exported by the dccp_tfrc_lib module.
 * interface to automatically track highest-received seqno;
 * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1);
 * a generic function to test for `data packets' as per  RFC 4340, sec. 7.7.


Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
---
 net/dccp/ccids/lib/packet_history.c |  126 ++++++++++++++++++++++++++++---
 net/dccp/ccids/lib/packet_history.h |  144 +++++++++++++++++++++++++++++++++++-
 net/dccp/ccids/lib/tfrc_module.c    |   26 ++++--
 net/dccp/dccp.h                     |   12 +++
 4 files changed, 285 insertions(+), 23 deletions(-)

--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -1,3 +1,5 @@
+#ifndef _DCCP_PKT_HIST_
+#define _DCCP_PKT_HIST_
 /*
  *  Packet RX/TX history data structures and routines for TFRC-based protocols.
  *
@@ -32,10 +34,6 @@
  *  along with this program; if not, write to the Free Software
  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
-
-#ifndef _DCCP_PKT_HIST_
-#define _DCCP_PKT_HIST_
-
 #include <linux/ktime.h>
 #include <linux/list.h>
 #include <linux/slab.h>
@@ -43,9 +41,13 @@
 
 /* Number of later packets received before one is considered lost */
 #define TFRC_RECV_NUM_LATE_LOSS	 3
+/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */
+#define NDUPACK 3
 
 #define TFRC_WIN_COUNT_PER_RTT	 4
 #define TFRC_WIN_COUNT_LIMIT	16
+/* Subtraction a-b modulo-16, respects circular wrap-around */
+#define SUB16(a,b)		(((a) + 16 - (b)) & 0xF)
 
 struct tfrc_tx_hist_entry;
 
@@ -66,6 +68,23 @@ struct dccp_rx_hist_entry {
 	ktime_t		 dccphrx_tstamp;
 };
 
+
+/**
+ *   tfrc_rx_hist_entry  -  Store information about a single received packet
+ *   @seqno:	DCCP packet sequence number
+ *   @ccval:	window counter value of packet (RFC 4342, 8.1)
+ *   @ptype:	the type (5.1) of the packet
+ *   @ndp:	the NDP count (if any) of the packet
+ *   @stamp:	actual receive time of packet
+ */
+struct tfrc_rx_hist_entry {
+	u64		seqno:48,
+			ccval:4,
+			ptype:4;
+	u32		ndp;
+	ktime_t		stamp;
+};
+
 struct dccp_rx_hist {
 	struct kmem_cache *dccprxh_slab;
 };
@@ -73,6 +92,123 @@ struct dccp_rx_hist {
 extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
 extern void 		dccp_rx_hist_delete(struct dccp_rx_hist *hist);
 
+/**
+ *   tfrc_rx_hist  -  RX history structure for TFRC-based protocols
+ *
+ *   @ring:		Packet history for RTT sampling and loss detection
+ *   @loss_count:	Number of entries in circular history
+ *   @loss_start:	Movable index (for loss detection)
+ *   @rtt_sample_prev:  Used during RTT sampling, points to candidate entry
+ */
+struct tfrc_rx_hist {
+	struct tfrc_rx_hist_entry	*ring[NDUPACK + 1];
+	u8				loss_count:2,
+					loss_start:2;
+#define rtt_sample_prev			loss_start
+};
+
+/*
+ * Macros for loss detection.
+ * @loss_prev:  entry with highest-received-seqno before loss was detected
+ * @hist_index: index to reach n-th entry after loss_start
+ * @hist_entry: return the n-th history entry  after loss_start
+ * @last_rcv:   entry with highest-received-seqno so far
+ */
+#define loss_prev(h)		(h)->ring[(h)->loss_start]
+#define hist_index(h, n)	(((h)->loss_start + (n)) & NDUPACK)
+#define hist_entry(h, n)	(h)->ring[hist_index(h, n)]
+#define last_rcv(h)		(h)->ring[hist_index(h, (h)->loss_count)]
+
+/*
+ * Macros to access history entries for RTT sampling.
+ * @rtt_last_s: reference entry to compute RTT samples against
+ * @rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry
+ */
+#define rtt_last_s(h)		(h)->ring[0]
+#define rtt_prev_s(h)		(h)->ring[(h)->rtt_sample_prev]
+
+/* 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_loss_pending(struct tfrc_rx_hist *h)
+{
+	return h->loss_count;
+}
+
+/* any data packets missing between last reception and skb ? */
+static inline int tfrc_rx_new_loss_indicated(struct tfrc_rx_hist *h,
+					     struct sk_buff *skb, u32 ndp)
+{
+	int delta = dccp_delta_seqno(last_rcv(h)->seqno,
+				     DCCP_SKB_CB(skb)->dccpd_seq);
+
+	if (delta > 1 && ndp < delta)
+		tfrc_rx_hist_loss_indicated(h);
+
+	return tfrc_rx_loss_pending(h);
+}
+
+/* has the packet contained in skb been seen before ? */
+static inline int tfrc_rx_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
+{
+	const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq;
+	int i;
+
+	if (dccp_delta_seqno(loss_prev(h)->seqno, seq) <= 0)
+		return 1;
+
+	for (i = 1; i <= h->loss_count; i++)
+		if (hist_entry(h, i)->seqno == seq)
+			return 1;
+
+	return 0;
+}
+
+/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */
+static inline 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(hist_entry(h, e1)->seqno,
+				hist_entry(h, e2)->seqno);
+}
+
+static inline 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;
+}
+
+static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *new,
+					        struct sk_buff *skb, u32 ndp)
+{
+	const struct dccp_hdr *dh = dccp_hdr(skb);
+
+	new->seqno = DCCP_SKB_CB(skb)->dccpd_seq;
+	new->ccval = dh->dccph_ccval;
+	new->ptype = dh->dccph_type;
+	new->ndp   = ndp;
+	new->stamp = ktime_get_real();
+}
+
+/* commit packet details of skb to history (record highest received seqno) */
+static inline void tfrc_rx_hist_update(struct tfrc_rx_hist *h,
+				       struct sk_buff *skb, u32 ndp)
+{
+	tfrc_rx_hist_entry_from_skb(last_rcv(h), skb, ndp);
+}
+
+extern u32  tfrc_rx_sample_rtt(struct tfrc_rx_hist *, struct sk_buff *);
+extern int  tfrc_rx_hist_init(struct tfrc_rx_hist *);
+extern void tfrc_rx_hist_cleanup(struct tfrc_rx_hist *);
+
 static inline struct dccp_rx_hist_entry *
 			dccp_rx_hist_entry_new(struct dccp_rx_hist *hist,
 					       const u32 ndp,
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -34,7 +34,6 @@
  *  along with this program; if not, write to the Free Software
  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
-
 #include <linux/string.h>
 #include "packet_history.h"
 
@@ -55,6 +54,22 @@ struct tfrc_tx_hist_entry {
  */
 static struct kmem_cache *tfrc_tx_hist;
 
+int __init tx_packet_history_init(void)
+{
+	tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist",
+					 sizeof(struct tfrc_tx_hist_entry), 0,
+					 SLAB_HWCACHE_ALIGN, NULL);
+	return tfrc_tx_hist == NULL ? -ENOBUFS : 0;
+}
+
+void tx_packet_history_cleanup(void)
+{
+	if (tfrc_tx_hist != NULL) {
+		kmem_cache_destroy(tfrc_tx_hist);
+		tfrc_tx_hist = NULL;
+	}
+}
+
 static struct tfrc_tx_hist_entry *
 	tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno)
 {
@@ -264,6 +279,55 @@ void dccp_rx_hist_add_packet(struct dccp
 
 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
 
+static struct kmem_cache *tfrc_rxh_cache;
+
+int __init rx_packet_history_init(void)
+{
+	tfrc_rxh_cache = kmem_cache_create("tfrc_rxh_cache",
+					   sizeof(struct tfrc_rx_hist_entry),
+					   0, SLAB_HWCACHE_ALIGN, NULL);
+	return tfrc_rxh_cache == NULL ? -ENOBUFS : 0;
+}
+
+void rx_packet_history_cleanup(void)
+{
+	if (tfrc_rxh_cache != NULL) {
+		kmem_cache_destroy(tfrc_rxh_cache);
+		tfrc_rxh_cache = NULL;
+	}
+}
+
+int tfrc_rx_hist_init(struct tfrc_rx_hist *h)
+{
+	int i;
+
+	for (i = 0; i <= NDUPACK; i++) {
+		h->ring[i] = kmem_cache_alloc(tfrc_rxh_cache, GFP_ATOMIC);
+		if (h->ring[i] == NULL)
+			goto out_free;
+	}
+	h->loss_count = h->loss_start = 0;
+	return 0;
+
+out_free:
+	while (i-- != 0) {
+		kmem_cache_free(tfrc_rxh_cache, h->ring[i]);
+		h->ring[i] = 0;
+	}
+	return -ENOBUFS;
+}
+EXPORT_SYMBOL_GPL(tfrc_rx_hist_init);
+
+void tfrc_rx_hist_cleanup(struct tfrc_rx_hist *h)
+{
+	int i;
+
+	for (i=0; i <= NDUPACK; i++)
+		if (h->ring[i] != NULL)
+			kmem_cache_free(tfrc_rxh_cache, h->ring[i]);
+}
+EXPORT_SYMBOL_GPL(tfrc_rx_hist_cleanup);
+
 void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
 {
 	struct dccp_rx_hist_entry *entry, *next;
@@ -276,18 +340,56 @@ void dccp_rx_hist_purge(struct dccp_rx_h
 
 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 
-int __init packet_history_init(void)
+/**
+ * tfrc_rx_sample_rtt  -  Sample RTT from timestamp / CCVal
+ * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able
+ * to compute a sample with given data - calling function should check this.
+ */
+u32 tfrc_rx_sample_rtt(struct tfrc_rx_hist *h, struct sk_buff *skb)
 {
-	tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist",
-					 sizeof(struct tfrc_tx_hist_entry), 0,
-					 SLAB_HWCACHE_ALIGN, NULL);
-	return tfrc_tx_hist == NULL ? -ENOBUFS : 0;
-}
+	u32 sample = 0,
+	    delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, rtt_last_s(h)->ccval);
 
-void __exit packet_history_exit(void)
-{
-	if (tfrc_tx_hist != NULL) {
-		kmem_cache_destroy(tfrc_tx_hist);
-		tfrc_tx_hist = NULL;
+	if (delta_v < 1 || delta_v > 4) {	/* unsuitable CCVal delta */
+
+		if (h->rtt_sample_prev == 2) {	/* previous candidate stored */
+			sample = SUB16(rtt_prev_s(h)->ccval,
+				       rtt_last_s(h)->ccval);
+			if (sample)
+				sample = 4 / sample
+				       * ktime_us_delta(rtt_prev_s(h)->stamp,
+							rtt_last_s(h)->stamp);
+			else    /*
+				 * FIXME: This condition is in principle not
+				 * possible but occurs when CCID is used for
+				 * two-way data traffic. I have tried to trace
+				 * it, but the cause does not seem to be here.
+				 */
+				DCCP_BUG("please report to dccp@vger.kernel.org"
+					 " => prev = %u, last = %u",
+					 rtt_prev_s(h)->ccval,
+					 rtt_last_s(h)->ccval);
+		} else if (delta_v < 1) {
+			h->rtt_sample_prev = 1;
+			goto keep_ref_for_next_time;
+		}
+
+	} else if (delta_v == 4) {     /* optimal match */
+		sample = ktime_to_us(net_timedelta(rtt_last_s(h)->stamp));
+
+	} else	{		       /* suboptimal match */
+		h->rtt_sample_prev = 2;
+		goto keep_ref_for_next_time;
+	}
+
+	if (unlikely(sample > DCCP_SANE_RTT_MAX)) {
+		DCCP_WARN("RTT sample %u too large, using max\n", sample);
+		sample = DCCP_SANE_RTT_MAX;
 	}
+
+	h->rtt_sample_prev = 0;	       /* use current entry as next reference */
+keep_ref_for_next_time:
+
+	return sample;
 }
+EXPORT_SYMBOL_GPL(tfrc_rx_sample_rtt);
--- a/net/dccp/dccp.h
+++ b/net/dccp/dccp.h
@@ -334,6 +334,7 @@ struct dccp_skb_cb {
 
 #define DCCP_SKB_CB(__skb) ((struct dccp_skb_cb *)&((__skb)->cb[0]))
 
+/* RFC 4340, sec. 7.7 */
 static inline int dccp_non_data_packet(const struct sk_buff *skb)
 {
 	const __u8 type = DCCP_SKB_CB(skb)->dccpd_type;
@@ -346,6 +347,17 @@ static inline int dccp_non_data_packet(c
 	       type == DCCP_PKT_SYNCACK;
 }
 
+/* RFC 4340, sec. 7.7 */
+static inline int dccp_data_packet(const struct sk_buff *skb)
+{
+	const __u8 type = DCCP_SKB_CB(skb)->dccpd_type;
+
+	return type == DCCP_PKT_DATA	 ||
+	       type == DCCP_PKT_DATAACK  ||
+	       type == DCCP_PKT_REQUEST  ||
+	       type == DCCP_PKT_RESPONSE;
+}
+
 static inline int dccp_packet_without_ack(const struct sk_buff *skb)
 {
 	const __u8 type = DCCP_SKB_CB(skb)->dccpd_type;
--- a/net/dccp/ccids/lib/tfrc_module.c
+++ b/net/dccp/ccids/lib/tfrc_module.c
@@ -8,8 +8,10 @@
 #include "tfrc.h"
 
 /* Initialisation / Clean-up routines */
-extern int  packet_history_init(void);
-extern void packet_history_exit(void);
+extern int  tx_packet_history_init(void);
+extern int  rx_packet_history_init(void);
+extern void tx_packet_history_cleanup(void);
+extern void rx_packet_history_cleanup(void);
 
 extern int  dccp_li_init(void);
 extern void dccp_li_exit(void);
@@ -24,11 +26,20 @@ static int __init tfrc_module_init(void)
 {
 	int rc = dccp_li_init();
 
-	if (rc == 0)
-		rc = packet_history_init();
-	if (rc == 0)
+	if (rc)
 		goto out;
 
+	rc = tx_packet_history_init();
+	if (rc)
+		goto out_free_loss_intervals;
+
+	rc = rx_packet_history_init();
+	if (rc)
+		goto out_free_tx_history;
+	return 0;
+
+out_free_tx_history:
+	tx_packet_history_cleanup();
 out_free_loss_intervals:
 	dccp_li_exit();
 out:
@@ -38,8 +49,9 @@ module_init(tfrc_module_init);
 
 static void __exit tfrc_module_exit(void)
 {
-	packet_history_exit();
-	dccp_li_exit();
+	rx_packet_history_cleanup();
+	tx_packet_history_cleanup();
+	dccp_li_exit();
 }
 module_exit(tfrc_module_exit);
 

[PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

This fixes a problem in the initial revision of the patch: The loss interval
history was not de-allocated when the initialisation of the packet history
failed.  The identification of this problem is also thanks due to Arnaldo.

The interdiff to the previous revision is:

	--- b/net/dccp/ccids/lib/tfrc_module.c
	+++ b/net/dccp/ccids/lib/tfrc_module.c
	@@ -26,7 +26,12 @@
	 
		if (rc == 0)
			rc = packet_history_init();
	+	if (rc == 0)
	+		goto out;
	 
	+out_free_loss_intervals:
	+	dccp_li_exit();
	+out:
		return rc;
	 }

-------------------------> Patch v2 <---------------------------------------
[TFRC]: Provide central source file and debug facility

This patch changes the tfrc_lib module in the following manner:

 (1) a dedicated tfrc_module source file  (this is later populated 
     with TX/RX hist and LI Database routines);
 (2) a dedicated tfrc_pr_debug macro with toggle switch `tfrc_debug'.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
---
 net/dccp/ccids/Kconfig              |   12 +++++---
 net/dccp/ccids/lib/Makefile         |    3 +-
 net/dccp/ccids/lib/loss_interval.c  |    2 -
 net/dccp/ccids/lib/packet_history.c |   28 ++------------------
 net/dccp/ccids/lib/packet_history.h |    3 --
 net/dccp/ccids/lib/tfrc.h           |   17 +++++++++---
 net/dccp/ccids/lib/tfrc_module.c    |   50 ++++++++++++++++++++++++++++++++++++
 7 files changed, 78 insertions(+), 37 deletions(-)

--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -39,8 +39,7 @@
 #include <linux/ktime.h>
 #include <linux/list.h>
 #include <linux/slab.h>
-
-#include "../../dccp.h"
+#include "tfrc.h"
 
 /* Number of later packets received before one is considered lost */
 #define TFRC_RECV_NUM_LATE_LOSS	 3
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -35,7 +35,6 @@
  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
 
-#include <linux/module.h>
 #include <linux/string.h>
 #include "packet_history.h"
 
@@ -277,39 +276,18 @@ void dccp_rx_hist_purge(struct dccp_rx_h
 
 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 
-extern int __init dccp_li_init(void);
-extern void dccp_li_exit(void);
-
-static __init int packet_history_init(void)
+int __init packet_history_init(void)
 {
-	if (dccp_li_init() != 0)
-		goto out;
-
 	tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist",
 					 sizeof(struct tfrc_tx_hist_entry), 0,
 					 SLAB_HWCACHE_ALIGN, NULL);
-	if (tfrc_tx_hist == NULL)
-		goto out_li_exit;
-
-	return 0;
-out_li_exit:
-	dccp_li_exit();
-out:
-	return -ENOBUFS;
+	return tfrc_tx_hist == NULL ? -ENOBUFS : 0;
 }
-module_init(packet_history_init);
 
-static __exit void packet_history_exit(void)
+void __exit packet_history_exit(void)
 {
 	if (tfrc_tx_hist != NULL) {
 		kmem_cache_destroy(tfrc_tx_hist);
 		tfrc_tx_hist = NULL;
 	}
-	dccp_li_exit();
 }
-module_exit(packet_history_exit);
-
-MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, "
-	      "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
-MODULE_DESCRIPTION("DCCP TFRC library");
-MODULE_LICENSE("GPL");
--- a/net/dccp/ccids/lib/tfrc.h
+++ b/net/dccp/ccids/lib/tfrc.h
@@ -3,10 +3,11 @@
 /*
  *  net/dccp/ccids/lib/tfrc.h
  *
- *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
- *  Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz>
- *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
- *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
+ *  Copyright (c) 2007   The University of Aberdeen, Scotland, UK
+ *  Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand.
+ *  Copyright (c) 2005-6 Ian McDonald <ian.mcdonald@jandi.co.nz>
+ *  Copyright (c) 2005   Arnaldo Carvalho de Melo <acme@conectiva.com.br>
+ *  Copyright (c) 2003   Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
@@ -15,6 +16,14 @@
  */
 #include <linux/types.h>
 #include <asm/div64.h>
+#include "../../dccp.h"
+
+#ifdef CONFIG_IP_DCCP_TFRC_DEBUG
+extern int tfrc_debug;
+#define tfrc_pr_debug(format, a...)	DCCP_PR_DEBUG(tfrc_debug, format, ##a)
+#else
+#define tfrc_pr_debug(format, a...)
+#endif
 
 /* integer-arithmetic divisions of type (a * 1000000)/b */
 static inline u64 scaled_div(u64 a, u32 b)
--- /dev/null
+++ b/net/dccp/ccids/lib/tfrc_module.c
@@ -0,0 +1,50 @@
+/*
+ * TFRC: main module holding the pieces of the TFRC library together
+ *
+ * Copyright (c) 2007   The University of Aberdeen, Scotland, UK
+ */
+#include <linux/module.h>
+#include <linux/moduleparam.h>
+#include "tfrc.h"
+
+/* Initialisation / Clean-up routines */
+extern int  packet_history_init(void);
+extern void packet_history_exit(void);
+
+extern int  dccp_li_init(void);
+extern void dccp_li_exit(void);
+
+#ifdef CONFIG_IP_DCCP_TFRC_DEBUG
+int tfrc_debug;
+module_param(tfrc_debug, bool, 0444);
+MODULE_PARM_DESC(tfrc_debug, "Enable debug messages");
+#endif
+
+static int __init tfrc_module_init(void)
+{
+	int rc = dccp_li_init();
+
+	if (rc == 0)
+		rc = packet_history_init();
+	if (rc == 0)
+		goto out;
+
+out_free_loss_intervals:
+	dccp_li_exit();
+out:
+	return rc;
+}
+module_init(tfrc_module_init);
+
+static void __exit tfrc_module_exit(void)
+{
+	packet_history_exit();
+	dccp_li_exit();
+}
+module_exit(tfrc_module_exit);
+
+MODULE_AUTHOR("Gerrit Renker <gerrit@erg.abdn.ac.uk>, "
+	      "Ian McDonald <ian.mcdonald@jandi.co.nz>, "
+	      "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
+MODULE_DESCRIPTION("DCCP TFRC library");
+MODULE_LICENSE("GPL");
--- a/net/dccp/ccids/lib/Makefile
+++ b/net/dccp/ccids/lib/Makefile
@@ -1,3 +1,4 @@
 obj-$(CONFIG_IP_DCCP_TFRC_LIB) += dccp_tfrc_lib.o
 
-dccp_tfrc_lib-y := loss_interval.o packet_history.o tfrc_equation.o
+dccp_tfrc_lib-y := tfrc_module.o    tfrc_equation.o \
+                   packet_history.o loss_interval.o
--- a/net/dccp/ccids/Kconfig
+++ b/net/dccp/ccids/Kconfig
@@ -63,10 +63,6 @@ config IP_DCCP_CCID3
 
 	  If in doubt, say M.
 
-config IP_DCCP_TFRC_LIB
-	depends on IP_DCCP_CCID3
-	def_tristate IP_DCCP_CCID3
-
 config IP_DCCP_CCID3_DEBUG
 	  bool "CCID3 debugging messages"
 	  depends on IP_DCCP_CCID3
@@ -110,5 +106,13 @@ config IP_DCCP_CCID3_RTO
 	    is serious network congestion: experimenting with larger values should
 	    therefore not be performed on WANs.
 
+# The TFRC Library: currently only has CCID 3 as customer
+config IP_DCCP_TFRC_LIB
+	depends on IP_DCCP_CCID3
+	def_tristate IP_DCCP_CCID3
+
+config IP_DCCP_TFRC_DEBUG
+	bool
+	default y if IP_DCCP_CCID3_DEBUG
 
 endmenu
--- a/net/dccp/ccids/lib/loss_interval.c
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -285,7 +285,7 @@ int __init dccp_li_init(void)
 	return dccp_li_cachep == NULL ? -ENOBUFS : 0;
 }
 
-void dccp_li_exit(void)
+void __exit dccp_li_exit(void)
 {
 	if (dccp_li_cachep != NULL) {
 		kmem_cache_destroy(dccp_li_cachep);

[PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

This patch removes the following redundancies:
  * ccid3_hc_rx_update_s() is only called for data packets (that is what it should be called for);
  * each call to ccid3_hc_rx_update_s() is wrapped inside a "if (is_data_packet)" test';
  * therefore testing each time if "len > 0" is redundant (pointed out by Arnaldo);
  * no other code calls this function, hence the inline function can go.

Also replaced the first call to updating s with direct assignment of `payload_size'; this has also
been pointed out by Arnaldo.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/ccid3.c |   13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -654,12 +654,6 @@ static void ccid3_hc_rx_set_state(struct
 	hcrx->ccid3hcrx_state = state;
 }
 
-static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len)
-{
-	if (likely(len > 0))	/* don't update on empty packets (e.g. ACKs) */
-		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, len, 9);
-}
-
 static void ccid3_hc_rx_send_feedback(struct sock *sk, struct sk_buff *skb,
 				      enum ccid3_fback_type fbtype)
 {
@@ -788,8 +782,8 @@ static void ccid3_hc_rx_packet_recv(stru
 	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
 		if (is_data_packet) {
 			do_feedback = FBACK_INITIAL;
+			hcrx->ccid3hcrx_s = payload_size;
 			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
-			ccid3_hc_rx_update_s(hcrx, payload_size);
 		}
 		goto update_records;
 	}
@@ -798,7 +792,10 @@ static void ccid3_hc_rx_packet_recv(stru
 		goto done_receiving;
 
 	if (is_data_packet) {
-		ccid3_hc_rx_update_s(hcrx, payload_size);
+		/*
+		 * Update moving-average of s and the sum of received payload bytes
+		 */
+		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload_size, 9);
 		hcrx->ccid3hcrx_bytes_recv += payload_size;
 	}
 

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 11:19:46AM +0000, Gerrit Renker escreveu:
> This patch removes the following redundancies:
>   * ccid3_hc_rx_update_s() is only called for data packets (that is what it should be called for);
>   * each call to ccid3_hc_rx_update_s() is wrapped inside a "if (is_data_packet)" test';
>   * therefore testing each time if "len > 0" is redundant (pointed out by Arnaldo);
>   * no other code calls this function, hence the inline function can go.
> 
> Also replaced the first call to updating s with direct assignment of `payload_size'; this has also
> been pointed out by Arnaldo.
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
> ---
>  net/dccp/ccids/ccid3.c |   13 +++++--------
>  1 file changed, 5 insertions(+), 8 deletions(-)
> 
> --- a/net/dccp/ccids/ccid3.c
> +++ b/net/dccp/ccids/ccid3.c
> @@ -654,12 +654,6 @@ static void ccid3_hc_rx_set_state(struct
>  	hcrx->ccid3hcrx_state = state;
>  }
>  
> -static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len)
> -{
> -	if (likely(len > 0))	/* don't update on empty packets (e.g. ACKs) */
> -		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, len, 9);
> -}
> -
>  static void ccid3_hc_rx_send_feedback(struct sock *sk, struct sk_buff *skb,
>  				      enum ccid3_fback_type fbtype)
>  {
> @@ -788,8 +782,8 @@ static void ccid3_hc_rx_packet_recv(stru
>  	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
>  		if (is_data_packet) {
>  			do_feedback = FBACK_INITIAL;
> +			hcrx->ccid3hcrx_s = payload_size;
>  			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
> -			ccid3_hc_rx_update_s(hcrx, payload_size);

We have to set ccid3hcrx_bytes_recv to the payload_size here too, I'm
fixing this on the reworked patch that introduces the RX history.

>  		}
>  		goto update_records;
>  	}
> @@ -798,7 +792,10 @@ static void ccid3_hc_rx_packet_recv(stru
>  		goto done_receiving;
>  
>  	if (is_data_packet) {
> -		ccid3_hc_rx_update_s(hcrx, payload_size);
> +		/*
> +		 * Update moving-average of s and the sum of received payload bytes
> +		 */
> +		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload_size, 9);
>  		hcrx->ccid3hcrx_bytes_recv += payload_size;

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

| > @@ -788,8 +782,8 @@ static void ccid3_hc_rx_packet_recv(stru
| >  	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
| >  		if (is_data_packet) {
| >  			do_feedback = FBACK_INITIAL;
| > +			hcrx->ccid3hcrx_s = payload_size;
| >  			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
| > -			ccid3_hc_rx_update_s(hcrx, payload_size);
| 
| We have to set ccid3hcrx_bytes_recv to the payload_size here too, I'm
| fixing this on the reworked patch that introduces the RX history.
| 
I almost did the same error again by wanting to agree too prematurely.

But updating ccid3hcrx_bytes_recv is in fact not needed here and if it
would be done it would not have a useable effect. The reason is that the
first data packet will trigger the initial feedback; and in the initial
feedback packet X_recv (which is ccid3hcrx_bytes_recv / the_time_spent)
is set to 0 (RFC 3448, 6.3).

For this reason, updating bytes_recv for the first data packet is also not
in the flowchart on 
http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 01:55:11PM +0000, Gerrit Renker escreveu:
> | > @@ -788,8 +782,8 @@ static void ccid3_hc_rx_packet_recv(stru
> | >  	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
> | >  		if (is_data_packet) {
> | >  			do_feedback = FBACK_INITIAL;
> | > +			hcrx->ccid3hcrx_s = payload_size;
> | >  			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
> | > -			ccid3_hc_rx_update_s(hcrx, payload_size);
> | 
> | We have to set ccid3hcrx_bytes_recv to the payload_size here too, I'm
> | fixing this on the reworked patch that introduces the RX history.
> | 
> I almost did the same error again by wanting to agree too prematurely.
> 
> But updating ccid3hcrx_bytes_recv is in fact not needed here and if it
> would be done it would not have a useable effect. The reason is that the
> first data packet will trigger the initial feedback; and in the initial
> feedback packet X_recv (which is ccid3hcrx_bytes_recv / the_time_spent)
> is set to 0 (RFC 3448, 6.3).
> 
> For this reason, updating bytes_recv for the first data packet is also not
> in the flowchart on 
> http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/

OK, I will add a comment on the code stating why it is not needed so
that new people don't commit the same mistake again.

- Arnaldo

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 11:19:46AM +0000, Gerrit Renker escreveu:
> This patch removes the following redundancies:
>   * ccid3_hc_rx_update_s() is only called for data packets (that is what it should be called for);
>   * each call to ccid3_hc_rx_update_s() is wrapped inside a "if (is_data_packet)" test';
>   * therefore testing each time if "len > 0" is redundant (pointed out by Arnaldo);
>   * no other code calls this function, hence the inline function can go.
> 
> Also replaced the first call to updating s with direct assignment of `payload_size'; this has also
> been pointed out by Arnaldo.

Thanks, I folded this into the reorganized RX history handling patch,
together with reverting ccid3_hc_rx_packet_recv to very close to your
original patch, with this changes:

1. no need to calculate the payload size for non data packets as this
   value won't be used.
2. Initialize hcrx->ccid3hcrx_bytes_recv with the payload size when
   hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA.
3. tfrc_rx_hist_duplicate() is only called when ccid3hcrx_state !=
   TFRC_RSTATE_NO_DATA, so it doesn't need to goto the done_receiving
   label (that was removed as this was its only use) as do_feedback
   would always be CCID3_FBACK_NONE and so the test would always fail
   and no feedback would be sent, so just return right there.

Now it reads:

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);
	enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE;
	const u32 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp;
	const bool is_data_packet = dccp_data_packet(skb);

	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
		if (is_data_packet) {
			const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
			do_feedback = FBACK_INITIAL;
			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
			hcrx->ccid3hcrx_s =
				hcrx->ccid3hcrx_bytes_recv = payload_size;
		}
		goto update_records;
 	}

	if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb))
		return; /* done receiving */

	if (is_data_packet) {
		const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
		/*
		 * Update moving-average of s and the sum of received payload bytes
		 */
		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload_size, 9);
		hcrx->ccid3hcrx_bytes_recv += payload_size;
 	}

	/*
	 * Handle pending losses and otherwise check for new loss
	 */
	if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp))
		goto update_records;

	/*
	 * Handle data packets: RTT sampling and monitoring p
	 */
	if (unlikely(!is_data_packet))
		goto update_records;

	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);
		if (sample != 0)
			hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9);
	}

	/*
	 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3
	 */
	if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
		do_feedback = CCID3_FBACK_PERIODIC;

update_records:	
	tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);

	if (do_feedback)
		ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
}

Now to some questions and please bear with me as I haven't got to the
patches after this:

tfrc_rx_hist->loss_count as of now is a boolean, my understanding is
that you are counting loss events, i.e. it doesn't matter in:

/* 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);
}

if (delta - ndp) is > 1, i.e. tfrc_rx_hist->loss_count only indicates
that there was loss. But then in other parts of the code it assumes it
can be more than 1:

/**
 * tfrc_rx_hist  -  RX history structure for TFRC-based protocols
 *
 * @ring:		Packet history for RTT sampling and loss detection
 * @loss_count:		Number of entries in circular history
 * @loss_start:		Movable index (for loss detection)
 * @rtt_sample_prev:	Used during RTT sampling, points to candidate entry
 */
struct tfrc_rx_hist {
	struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1];
	u8			  loss_count:2,
				  loss_start:2;
#define rtt_sample_prev		  loss_start
};

There is space for TFRC_NDUPACK + 1 possible values in loss_count (:2)
and the comment says it is the number of entries in the circular
history, and also:

/* has the packet contained in skb been seen before? */
int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
{
	const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq;
	int i;

	if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0)
		return 1;

	for (i = 1; i <= h->loss_count; i++)
		if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq)
			return 1;

	return 0;
}

With the current code this will always check just one entry, as
loss_count only gets to 1 in tfrc_rx_hist_loss_indicated.

I'm not implying there is an error, I need to read the patches that
follow, I'm just trying to get over coding conventions and basic
algorithm sanity tests.

I'll look at your page looking for extra explanations about this.

- Arnaldo

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Gerrit Renker]

| Thanks, I folded this into the reorganized RX history handling patch,
| together with reverting ccid3_hc_rx_packet_recv to very close to your
| original patch, with this changes:
| 
| 1. no need to calculate the payload size for non data packets as this
|    value won't be used.
| 2. Initialize hcrx->ccid3hcrx_bytes_recv with the payload size when
|    hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA.
| 3. tfrc_rx_hist_duplicate() is only called when ccid3hcrx_state !=
|    TFRC_RSTATE_NO_DATA, so it doesn't need to goto the done_receiving
|    label (that was removed as this was its only use) as do_feedback
|    would always be CCID3_FBACK_NONE and so the test would always fail
|    and no feedback would be sent, so just return right there.
| 
| Now it reads:
| 
| 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);
| 	enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE;
| 	const u32 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp;
| 	const bool is_data_packet = dccp_data_packet(skb);
| 
| 	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
| 		if (is_data_packet) {
| 			const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
| 			do_feedback = FBACK_INITIAL;
| 			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
| 			hcrx->ccid3hcrx_s =
| 				hcrx->ccid3hcrx_bytes_recv = payload_size;

  ==> Please see other email regarding bytes_recv, but I think you already got that.
      Maybe one could then write
      	hcrx->ccid3hcrx_s = skb->len - dccp_hdr(skb)->dccph_doff * 4;
 
| 		}
| 		goto update_records;
|  	}
| 
| 	if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb))
| 		return; /* done receiving */
| 
| 	if (is_data_packet) {
| 		const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
| 		/*
| 		 * Update moving-average of s and the sum of received payload bytes
| 		 */
| 		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload_size, 9);
| 		hcrx->ccid3hcrx_bytes_recv += payload_size;
|  	}
| 
| 	/*
| 	 * Handle pending losses and otherwise check for new loss
| 	 */
| 	if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp))
| 		goto update_records;
| 
| 	/*
| 	 * Handle data packets: RTT sampling and monitoring p
| 	 */
| 	if (unlikely(!is_data_packet))
| 		goto update_records;
| 
| 	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);
==> If you like, you could add the original comment here that p=0 if no	loss occured, i.e.
		/*
		 * 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);
| 	}
| 
| 	/*
| 	 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3
| 	 */
| 	if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
| 		do_feedback = CCID3_FBACK_PERIODIC;
| 
| update_records:	
| 	tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);
| 
==>  here a jump label is missing. It is not needed by this patch and
     above you have replaced it with a return + comment, but it is needed in a later
     patch: when a new loss event occurs, the control jumps to `done_receiving' and
     sends a feedback packet with type FBACK_PARAM_CHANGE.
done_receiving:
| 	if (do_feedback)
| 		ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
| }
| 

| Now to some questions and please bear with me as I haven't got to the
| patches after this:
| 
| tfrc_rx_hist->loss_count as of now is a boolean, my understanding is
| that you are counting loss events, i.e. it doesn't matter in:
|
It is not a boolean, but uses a hidden trick which maybe should be commented:
 * here and in the TCP world NDUPACK = 3
 * hence the bitfield size for loss_count is 2 bits, which can express
   at most 3 = NDUPACK (that is why it is declared as loss_count:2)
 * the trick is that when the loss count increases beyond 3, it automatically 
   cycles back to 0 (although the code does not rely on that features
   and does this explicitly);
 * loss_start is the same


| /* 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);
| }
| 
| if (delta - ndp) is > 1, i.e. tfrc_rx_hist->loss_count only indicates
| that there was loss. But then in other parts of the code it assumes it
| can be more than 1:
In the above case the first loss is recorded in the history, which is
why loss_count is set to 1. Maybe it gets clearer in the next patch set,
which has three helper functions
 __one_after_loss: to deal with the first lost packet
 __two_after_loss: which deals when loss_count=2 packets are missing
 __three_after_loss is already a new loss event (3=NDUPACK), so that
   function only recycles the loss records



| /**
|  * tfrc_rx_hist  -  RX history structure for TFRC-based protocols
|  *
|  * @ring:		Packet history for RTT sampling and loss detection
|  * @loss_count:		Number of entries in circular history
|  * @loss_start:		Movable index (for loss detection)
|  * @rtt_sample_prev:	Used during RTT sampling, points to candidate entry
|  */
| struct tfrc_rx_hist {
| 	struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1];
| 	u8			  loss_count:2,
| 				  loss_start:2;
| #define rtt_sample_prev		  loss_start
| };
| 
| There is space for TFRC_NDUPACK + 1 possible values in loss_count (:2)
| and the comment says it is the number of entries in the circular
| history, and also:
| 
| /* has the packet contained in skb been seen before? */
| int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
| {
| 	const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq;
| 	int i;
| 
| 	if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0)
| 		return 1;
| 
| 	for (i = 1; i <= h->loss_count; i++)
| 		if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq)
| 			return 1;
| 
| 	return 0;
| }
| 
| With the current code this will always check just one entry, as
| loss_count only gets to 1 in tfrc_rx_hist_loss_indicated.
|
Again the resolution is in the next patch: 
 * when loss_count = 0 (no loss so far), loss_indicated() is called, sets loss_count = 2
 * when loss_count = 1, __one_after_loss() is called, which checks if this a genuine loss
  --> it then has the line
  	h->loss_count = 2;	/* second packet lost */
 * when loss_count = 2, __two_after_loss() is called,
   - this function returns 1 when the current packet indicates a genuine loss
   - in that case loss_count is set to 3
 * when loss_count = 3, __three_after_loss() is called, and the whole structure is recycled.

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 02:53:09PM +0000, Gerrit Renker escreveu:
> | Thanks, I folded this into the reorganized RX history handling patch,
> | together with reverting ccid3_hc_rx_packet_recv to very close to your
> | original patch, with this changes:
> | 
> | 1. no need to calculate the payload size for non data packets as this
> |    value won't be used.
> | 2. Initialize hcrx->ccid3hcrx_bytes_recv with the payload size when
> |    hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA.
> | 3. tfrc_rx_hist_duplicate() is only called when ccid3hcrx_state !=
> |    TFRC_RSTATE_NO_DATA, so it doesn't need to goto the done_receiving
> |    label (that was removed as this was its only use) as do_feedback
> |    would always be CCID3_FBACK_NONE and so the test would always fail
> |    and no feedback would be sent, so just return right there.
> | 
> | Now it reads:
> | 
> | 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);
> | 	enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE;
> | 	const u32 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp;
> | 	const bool is_data_packet = dccp_data_packet(skb);
> | 
> | 	if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
> | 		if (is_data_packet) {
> | 			const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
> | 			do_feedback = FBACK_INITIAL;
> | 			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
> | 			hcrx->ccid3hcrx_s =
> | 				hcrx->ccid3hcrx_bytes_recv = payload_size;
> 
>   ==> Please see other email regarding bytes_recv, but I think you already got that.
>       Maybe one could then write
>       	hcrx->ccid3hcrx_s = skb->len - dccp_hdr(skb)->dccph_doff * 4;

OK, I got that.
  
> | 		}
> | 		goto update_records;
> |  	}
> | 
> | 	if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb))
> | 		return; /* done receiving */
> | 
> | 	if (is_data_packet) {
> | 		const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
> | 		/*
> | 		 * Update moving-average of s and the sum of received payload bytes
> | 		 */
> | 		hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload_size, 9);
> | 		hcrx->ccid3hcrx_bytes_recv += payload_size;
> |  	}
> | 
> | 	/*
> | 	 * Handle pending losses and otherwise check for new loss
> | 	 */
> | 	if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp))
> | 		goto update_records;
> | 
> | 	/*
> | 	 * Handle data packets: RTT sampling and monitoring p
> | 	 */
> | 	if (unlikely(!is_data_packet))
> | 		goto update_records;
> | 
> | 	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);
> ==> If you like, you could add the original comment here that p=0 if no	loss occured, i.e.
> 		/*
> 		 * 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.
> 		 */

done

> | 		if (sample != 0)
> | 			hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9);
> | 	}
> | 
> | 	/*
> | 	 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3
> | 	 */
> | 	if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
> | 		do_feedback = CCID3_FBACK_PERIODIC;
> | 
> | update_records:	
> | 	tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);
> | 
> ==>  here a jump label is missing. It is not needed by this patch and
>      above you have replaced it with a return + comment, but it is needed in a later
>      patch: when a new loss event occurs, the control jumps to `done_receiving' and
>      sends a feedback packet with type FBACK_PARAM_CHANGE.

OK, I was wondering that the user for FBACK_PARAM_CHANGE in
ccid3_hc_rx_send_feedback was in another patch.

> done_receiving:

Ok, we can add the jump label when we make use of it

> | 	if (do_feedback)
> | 		ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
> | }
> | 
> 
> | Now to some questions and please bear with me as I haven't got to the
> | patches after this:
> | 
> | tfrc_rx_hist->loss_count as of now is a boolean, my understanding is
> | that you are counting loss events, i.e. it doesn't matter in:
> |
> It is not a boolean, but uses a hidden trick which maybe should be commented:
>  * here and in the TCP world NDUPACK = 3
>  * hence the bitfield size for loss_count is 2 bits, which can express
>    at most 3 = NDUPACK (that is why it is declared as loss_count:2)
>  * the trick is that when the loss count increases beyond 3, it automatically 
>    cycles back to 0 (although the code does not rely on that features
>    and does this explicitly);
>  * loss_start is the same

OK, will read the next patches with this in mind, thanks for the
explanations.

- Arnaldo

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 11:19:45AM +0000, Gerrit Renker escreveu:
> This fixes a problem in the initial revision of the patch: The loss interval
> history was not de-allocated when the initialisation of the packet history
> failed.  The identification of this problem is also thanks due to Arnaldo.
> 
> The interdiff to the previous revision is:
> 
> 	--- b/net/dccp/ccids/lib/tfrc_module.c
> 	+++ b/net/dccp/ccids/lib/tfrc_module.c
> 	@@ -26,7 +26,12 @@
> 	 
> 		if (rc == 0)
> 			rc = packet_history_init();
> 	+	if (rc == 0)
> 	+		goto out;
> 	 
> 	+out_free_loss_intervals:
> 	+	dccp_li_exit();
> 	+out:
> 		return rc;
> 	 }
> 

Ok, this one is kept on the series I have pending submission.

- Arnaldo

Re: [PATCH v2 0/3][BUG-FIX]: Test tree updates and bug fixes

[Arnaldo Carvalho de Melo]

Em Wed, Dec 05, 2007 at 11:19:44AM +0000, Gerrit Renker escreveu:
> This revision fixes a bug present in the per-socket allocation of RX history 
> entries; identification of this bug is thanks to Arnaldo Carvalho de Melo.
> 
> The bug was in not deallocating history entries when the allocation of 
> one array element failed. The solution in this revised patch set is the
> original one written by Arnaldo.

Ok, this one I posted with some other comments and explanations about
changes other than namespacing, renaming of some functions and removal
of functions not used in this patch.
 
- Arnaldo