4 files changed, 214 insertions, 184 deletions

diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index b876c9c81c6..2e8ef42721e 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -36,9 +36,100 @@
 
 #include <linux/module.h>
 #include <linux/string.h>
-
 #include "packet_history.h"
 
+/*
+ * 	Transmitter History Routines
+ */
+struct dccp_tx_hist *dccp_tx_hist_new(const char *name)
+{
+	struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
+	static const char dccp_tx_hist_mask[] = "tx_hist_%s";
+	char *slab_name;
+
+	if (hist == NULL)
+		goto out;
+
+	slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1,
+			    GFP_ATOMIC);
+	if (slab_name == NULL)
+		goto out_free_hist;
+
+	sprintf(slab_name, dccp_tx_hist_mask, name);
+	hist->dccptxh_slab = kmem_cache_create(slab_name,
+					     sizeof(struct dccp_tx_hist_entry),
+					       0, SLAB_HWCACHE_ALIGN,
+					       NULL, NULL);
+	if (hist->dccptxh_slab == NULL)
+		goto out_free_slab_name;
+out:
+	return hist;
+out_free_slab_name:
+	kfree(slab_name);
+out_free_hist:
+	kfree(hist);
+	hist = NULL;
+	goto out;
+}
+
+EXPORT_SYMBOL_GPL(dccp_tx_hist_new);
+
+void dccp_tx_hist_delete(struct dccp_tx_hist *hist)
+{
+	const char* name = kmem_cache_name(hist->dccptxh_slab);
+
+	kmem_cache_destroy(hist->dccptxh_slab);
+	kfree(name);
+	kfree(hist);
+}
+
+EXPORT_SYMBOL_GPL(dccp_tx_hist_delete);
+
+struct dccp_tx_hist_entry *
+	dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq)
+{
+	struct dccp_tx_hist_entry *packet = NULL, *entry;
+
+	list_for_each_entry(entry, list, dccphtx_node)
+		if (entry->dccphtx_seqno == seq) {
+			packet = entry;
+			break;
+		}
+
+	return packet;
+}
+
+EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry);
+
+void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list)
+{
+	struct dccp_tx_hist_entry *entry, *next;
+
+	list_for_each_entry_safe(entry, next, list, dccphtx_node) {
+		list_del_init(&entry->dccphtx_node);
+		dccp_tx_hist_entry_delete(hist, entry);
+	}
+}
+
+EXPORT_SYMBOL_GPL(dccp_tx_hist_purge);
+
+void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist,
+			      struct list_head *list,
+			      struct dccp_tx_hist_entry *packet)
+{
+	struct dccp_tx_hist_entry *next;
+
+	list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) {
+		list_del_init(&packet->dccphtx_node);
+		dccp_tx_hist_entry_delete(hist, packet);
+	}
+}
+
+EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older);
+
+/*
+ * 	Receiver History Routines
+ */
 struct dccp_rx_hist *dccp_rx_hist_new(const char *name)
 {
 	struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
@@ -83,18 +174,24 @@ void dccp_rx_hist_delete(struct dccp_rx_hist *hist)
 
 EXPORT_SYMBOL_GPL(dccp_rx_hist_delete);
 
-void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
+int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
+			    u8 *ccval)
 {
-	struct dccp_rx_hist_entry *entry, *next;
+	struct dccp_rx_hist_entry *packet = NULL, *entry;
 
-	list_for_each_entry_safe(entry, next, list, dccphrx_node) {
-		list_del_init(&entry->dccphrx_node);
-		kmem_cache_free(hist->dccprxh_slab, entry);
-	}
-}
+	list_for_each_entry(entry, list, dccphrx_node)
+		if (entry->dccphrx_seqno == seq) {
+			packet = entry;
+			break;
+		}
 
-EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
+	if (packet)
+		*ccval = packet->dccphrx_ccval;
 
+	return packet != NULL;
+}
+
+EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry);
 struct dccp_rx_hist_entry *
 		dccp_rx_hist_find_data_packet(const struct list_head *list)
 {
@@ -184,110 +281,18 @@ void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
 
 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
 
-struct dccp_tx_hist *dccp_tx_hist_new(const char *name)
-{
-	struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
-	static const char dccp_tx_hist_mask[] = "tx_hist_%s";
-	char *slab_name;
-
-	if (hist == NULL)
-		goto out;
-
-	slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1,
-			    GFP_ATOMIC);
-	if (slab_name == NULL)
-		goto out_free_hist;
-
-	sprintf(slab_name, dccp_tx_hist_mask, name);
-	hist->dccptxh_slab = kmem_cache_create(slab_name,
-					     sizeof(struct dccp_tx_hist_entry),
-					       0, SLAB_HWCACHE_ALIGN,
-					       NULL, NULL);
-	if (hist->dccptxh_slab == NULL)
-		goto out_free_slab_name;
-out:
-	return hist;
-out_free_slab_name:
-	kfree(slab_name);
-out_free_hist:
-	kfree(hist);
-	hist = NULL;
-	goto out;
-}
-
-EXPORT_SYMBOL_GPL(dccp_tx_hist_new);
-
-void dccp_tx_hist_delete(struct dccp_tx_hist *hist)
-{
-	const char* name = kmem_cache_name(hist->dccptxh_slab);
-
-	kmem_cache_destroy(hist->dccptxh_slab);
-	kfree(name);
-	kfree(hist);
-}
-
-EXPORT_SYMBOL_GPL(dccp_tx_hist_delete);
-
-struct dccp_tx_hist_entry *
-	dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq)
-{
-	struct dccp_tx_hist_entry *packet = NULL, *entry;
-
-	list_for_each_entry(entry, list, dccphtx_node)
-		if (entry->dccphtx_seqno == seq) {
-			packet = entry;
-			break;
-		}
-
-	return packet;
-}
-
-EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry);
-
-int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
-   u8 *ccval)
-{
-	struct dccp_rx_hist_entry *packet = NULL, *entry;
-
-	list_for_each_entry(entry, list, dccphrx_node)
-		if (entry->dccphrx_seqno == seq) {
-			packet = entry;
-			break;
-		}
-
-	if (packet)
-		*ccval = packet->dccphrx_ccval;
-
-	return packet != NULL;
-}
-
-EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry);
-
-void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist,
-			      struct list_head *list,
-			      struct dccp_tx_hist_entry *packet)
+void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
 {
-	struct dccp_tx_hist_entry *next;
+	struct dccp_rx_hist_entry *entry, *next;
 
-	list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) {
-		list_del_init(&packet->dccphtx_node);
-		dccp_tx_hist_entry_delete(hist, packet);
+	list_for_each_entry_safe(entry, next, list, dccphrx_node) {
+		list_del_init(&entry->dccphrx_node);
+		kmem_cache_free(hist->dccprxh_slab, entry);
 	}
 }
 
-EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older);
-
-void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list)
-{
-	struct dccp_tx_hist_entry *entry, *next;
-
-	list_for_each_entry_safe(entry, next, list, dccphtx_node) {
-		list_del_init(&entry->dccphtx_node);
-		dccp_tx_hist_entry_delete(hist, entry);
-	}
-}
+EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 
-EXPORT_SYMBOL_GPL(dccp_tx_hist_purge);
 
 MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, "
 	      "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index 9a8bcf224aa..1f960c19ea1 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -49,43 +49,27 @@
 #define TFRC_WIN_COUNT_PER_RTT	 4
 #define TFRC_WIN_COUNT_LIMIT	16
 
+/*
+ * 	Transmitter History data structures and declarations
+ */
 struct dccp_tx_hist_entry {
 	struct list_head dccphtx_node;
 	u64		 dccphtx_seqno:48,
-			 dccphtx_ccval:4,
 			 dccphtx_sent:1;
 	u32		 dccphtx_rtt;
 	struct timeval	 dccphtx_tstamp;
 };
 
-struct dccp_rx_hist_entry {
-	struct list_head dccphrx_node;
-	u64		 dccphrx_seqno:48,
-			 dccphrx_ccval:4,
-			 dccphrx_type:4;
-	u32		 dccphrx_ndp; /* In fact it is from 8 to 24 bits */
-	struct timeval	 dccphrx_tstamp;
-};
-
 struct dccp_tx_hist {
 	struct kmem_cache *dccptxh_slab;
 };
 
 extern struct dccp_tx_hist *dccp_tx_hist_new(const char *name);
-extern void dccp_tx_hist_delete(struct dccp_tx_hist *hist);
-
-struct dccp_rx_hist {
-	struct kmem_cache *dccprxh_slab;
-};
-
-extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
-extern void dccp_rx_hist_delete(struct dccp_rx_hist *hist);
-extern struct dccp_rx_hist_entry *
-		dccp_rx_hist_find_data_packet(const struct list_head *list);
+extern void 		    dccp_tx_hist_delete(struct dccp_tx_hist *hist);
 
 static inline struct dccp_tx_hist_entry *
-		dccp_tx_hist_entry_new(struct dccp_tx_hist *hist,
-				       const gfp_t prio)
+			dccp_tx_hist_entry_new(struct dccp_tx_hist *hist,
+					       const gfp_t prio)
 {
 	struct dccp_tx_hist_entry *entry = kmem_cache_alloc(hist->dccptxh_slab,
 							    prio);
@@ -96,18 +80,20 @@ static inline struct dccp_tx_hist_entry *
 	return entry;
 }
 
-static inline void dccp_tx_hist_entry_delete(struct dccp_tx_hist *hist,
-					     struct dccp_tx_hist_entry *entry)
+static inline struct dccp_tx_hist_entry *
+			dccp_tx_hist_head(struct list_head *list)
 {
-	if (entry != NULL)
-		kmem_cache_free(hist->dccptxh_slab, entry);
+	struct dccp_tx_hist_entry *head = NULL;
+
+	if (!list_empty(list))
+		head = list_entry(list->next, struct dccp_tx_hist_entry,
+				  dccphtx_node);
+	return head;
 }
 
 extern struct dccp_tx_hist_entry *
 			dccp_tx_hist_find_entry(const struct list_head *list,
 						const u64 seq);
-extern int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
-   u8 *ccval);
 
 static inline void dccp_tx_hist_add_entry(struct list_head *list,
 					  struct dccp_tx_hist_entry *entry)
@@ -115,30 +101,45 @@ static inline void dccp_tx_hist_add_entry(struct list_head *list,
 	list_add(&entry->dccphtx_node, list);
 }
 
+static inline void dccp_tx_hist_entry_delete(struct dccp_tx_hist *hist,
+					     struct dccp_tx_hist_entry *entry)
+{
+	if (entry != NULL)
+		kmem_cache_free(hist->dccptxh_slab, entry);
+}
+
+extern void dccp_tx_hist_purge(struct dccp_tx_hist *hist,
+			       struct list_head *list);
+
 extern void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist,
 				     struct list_head *list,
 				     struct dccp_tx_hist_entry *next);
 
-extern void dccp_tx_hist_purge(struct dccp_tx_hist *hist,
-			       struct list_head *list);
+/*
+ * 	Receiver History data structures and declarations
+ */
+struct dccp_rx_hist_entry {
+	struct list_head dccphrx_node;
+	u64		 dccphrx_seqno:48,
+			 dccphrx_ccval:4,
+			 dccphrx_type:4;
+	u32		 dccphrx_ndp; /* In fact it is from 8 to 24 bits */
+	struct timeval	 dccphrx_tstamp;
+};
 
-static inline struct dccp_tx_hist_entry *
-		dccp_tx_hist_head(struct list_head *list)
-{
-	struct dccp_tx_hist_entry *head = NULL;
+struct dccp_rx_hist {
+	struct kmem_cache *dccprxh_slab;
+};
 
-	if (!list_empty(list))
-		head = list_entry(list->next, struct dccp_tx_hist_entry,
-				  dccphtx_node);
-	return head;
-}
+extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
+extern void 		dccp_rx_hist_delete(struct dccp_rx_hist *hist);
 
 static inline struct dccp_rx_hist_entry *
-		     dccp_rx_hist_entry_new(struct dccp_rx_hist *hist,
-				     	    const struct sock *sk, 
-				     	    const u32 ndp, 
-					    const struct sk_buff *skb,
-					    const gfp_t prio)
+			dccp_rx_hist_entry_new(struct dccp_rx_hist *hist,
+					       const struct sock *sk,
+				     	       const u32 ndp,
+					       const struct sk_buff *skb,
+					       const gfp_t prio)
 {
 	struct dccp_rx_hist_entry *entry = kmem_cache_alloc(hist->dccprxh_slab,
 							    prio);
@@ -156,18 +157,8 @@ static inline struct dccp_rx_hist_entry *
 	return entry;
 }
 
-static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist *hist,
-					     struct dccp_rx_hist_entry *entry)
-{
-	if (entry != NULL)
-		kmem_cache_free(hist->dccprxh_slab, entry);
-}
-
-extern void dccp_rx_hist_purge(struct dccp_rx_hist *hist,
-			       struct list_head *list);
-
 static inline struct dccp_rx_hist_entry *
-		dccp_rx_hist_head(struct list_head *list)
+			dccp_rx_hist_head(struct list_head *list)
 {
 	struct dccp_rx_hist_entry *head = NULL;
 
@@ -177,6 +168,27 @@ static inline struct dccp_rx_hist_entry *
 	return head;
 }
 
+extern int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
+   				   u8 *ccval);
+extern struct dccp_rx_hist_entry *
+		dccp_rx_hist_find_data_packet(const struct list_head *list);
+
+extern void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
+				    struct list_head *rx_list,
+				    struct list_head *li_list,
+				    struct dccp_rx_hist_entry *packet,
+				    u64 nonloss_seqno);
+
+static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist *hist,
+					     struct dccp_rx_hist_entry *entry)
+{
+	if (entry != NULL)
+		kmem_cache_free(hist->dccprxh_slab, entry);
+}
+
+extern void dccp_rx_hist_purge(struct dccp_rx_hist *hist,
+			       struct list_head *list);
+
 static inline int
 	dccp_rx_hist_entry_data_packet(const struct dccp_rx_hist_entry *entry)
 {
@@ -184,12 +196,6 @@ static inline int
 	       entry->dccphrx_type == DCCP_PKT_DATAACK;
 }
 
-extern void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
-				   struct list_head *rx_list,
-				   struct list_head *li_list,
-				   struct dccp_rx_hist_entry *packet,
-				   u64 nonloss_seqno);
-
 extern u64 dccp_rx_hist_detect_loss(struct list_head *rx_list,
 				    struct list_head *li_list, u8 *win_loss);
 
diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h
index 45f30f59ea2..faf5f7e219e 100644
--- a/net/dccp/ccids/lib/tfrc.h
+++ b/net/dccp/ccids/lib/tfrc.h
@@ -13,8 +13,29 @@
  *  the Free Software Foundation; either version 2 of the License, or
  *  (at your option) any later version.
  */
-
 #include <linux/types.h>
+#include <asm/div64.h>
+
+/* integer-arithmetic divisions of type (a * 1000000)/b */
+static inline u64 scaled_div(u64 a, u32 b)
+{
+	BUG_ON(b==0);
+	a *= 1000000;
+	do_div(a, b);
+	return a;
+}
+
+static inline u32 scaled_div32(u64 a, u32 b)
+{
+	u64 result = scaled_div(a, b);
+
+	if (result > UINT_MAX) {
+		DCCP_CRIT("Overflow: a(%llu)/b(%u) > ~0U",
+			  (unsigned long long)a, b);
+		return UINT_MAX;
+	}
+	return result;
+}
 
 extern u32 tfrc_calc_x(u16 s, u32 R, u32 p);
 extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue);
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index ddac2c511e2..90009fd77e1 100644
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -13,7 +13,6 @@
  */
 
 #include <linux/module.h>
-#include <asm/div64.h>
 #include "../../dccp.h"
 #include "tfrc.h"
 
@@ -616,15 +615,12 @@ static inline u32 tfrc_binsearch(u32 fval, u8 small)
  *  @R: RTT                  scaled by 1000000   (i.e., microseconds)
  *  @p: loss ratio estimate  scaled by 1000000
  *  Returns X_calc           in bytes per second (not scaled).
- *
- * Note: DO NOT alter this code unless you run test cases against it,
- *       as the code has been optimized to stop underflow/overflow.
  */
 u32 tfrc_calc_x(u16 s, u32 R, u32 p)
 {
-	int index;
+	u16 index;
 	u32 f;
-	u64 tmp1, tmp2;
+	u64 result;
 
 	/* check against invalid parameters and divide-by-zero   */
 	BUG_ON(p >  1000000);		/* p must not exceed 100%   */
@@ -650,15 +646,17 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
 		f = tfrc_calc_x_lookup[index][0];
 	}
 
-	/* The following computes X = s/(R*f(p)) in bytes per second. Since f(p)
-	 * and R are both scaled by 1000000, we need to multiply by 1000000^2.
-	 * ==> DO NOT alter this unless you test against overflow on 32 bit   */
-	tmp1 = ((u64)s * 100000000);
-	tmp2 = ((u64)R * (u64)f);
-	do_div(tmp2, 10000);
-	do_div(tmp1, tmp2); 
-
-	return (u32)tmp1; 
+	/*
+	 * Compute X = s/(R*f(p)) in bytes per second.
+	 * Since f(p) and R are both scaled by 1000000, we need to multiply by
+	 * 1000000^2. To avoid overflow, the result is computed in two stages.
+	 * This works under almost all reasonable operational conditions, for a
+	 * wide range of parameters. Yet, should some strange combination of
+	 * parameters result in overflow, the use of scaled_div32 will catch
+	 * this and return UINT_MAX - which is a logically adequate consequence.
+	 */
+	result = scaled_div(s, R);
+	return scaled_div32(result, f);
 }
 
 EXPORT_SYMBOL_GPL(tfrc_calc_x);