Skip to contentSkip to conversation

: Revert code shifts

PATCH In review Gerrit Renker 2 participants 3 messages Jun 17, 2007 – Jun 27, 2007 Networking

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 : Revert code shifts

[CCID3]: Revert code shifts

This reverts those recent changes in the CCID3 codebase that overlap 100% with code I have developed independently.

All functions and each line in this code set is either rewritten or removed in my patch set, so this patch reflects all the code overlap, nothing more.

---
 net/dccp/ccids/ccid3.c             |  175 +++++++++++++++++++++++++--
 net/dccp/ccids/lib/loss_interval.c |  238 ++++++-------------------------------
 net/dccp/ccids/lib/loss_interval.h |   42 +++++-
 3 files changed, 242 insertions(+), 213 deletions(-)
net/dccp/ccids/ccid3.c +164 -11
@@ -49,6 +49,7 @@ static int ccid3_debug;
 
 static struct dccp_tx_hist *ccid3_tx_hist;
 static struct dccp_rx_hist *ccid3_rx_hist;
+static struct dccp_li_hist *ccid3_li_hist;
 
 /*
  *	Transmitter Half-Connection Routines
@@ -811,6 +812,154 @@ static int ccid3_hc_rx_insert_options(st
 	return 0;
 }
 
+/* calculate first loss interval
+ *
+ * returns estimated loss interval in usecs */
+
+static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
+{
+	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
+	struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
+	u32 x_recv, p;
+	suseconds_t rtt, delta;
+	struct timeval tstamp = { 0, };
+	int interval = 0;
+	int win_count = 0;
+	int step = 0;
+	u64 fval;
+
+	list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
+				 dccphrx_node) {
+		if (dccp_rx_hist_entry_data_packet(entry)) {
+			tail = entry;
+
+			switch (step) {
+			case 0:
+				tstamp	  = entry->dccphrx_tstamp;
+				win_count = entry->dccphrx_ccval;
+				step = 1;
+				break;
+			case 1:
+				interval = win_count - entry->dccphrx_ccval;
+				if (interval < 0)
+					interval += TFRC_WIN_COUNT_LIMIT;
+				if (interval > 4)
+					goto found;
+				break;
+			}
+		}
+	}
+
+	if (unlikely(step = 0)) {
+		DCCP_WARN("%s(%p), packet history has no data packets!\n",
+			  dccp_role(sk), sk);
+		return ~0;
+	}
+
+	if (unlikely(interval = 0)) {
+		DCCP_WARN("%s(%p), Could not find a win_count interval > 0."
+			  "Defaulting to 1\n", dccp_role(sk), sk);
+		interval = 1;
+	}
+found:
+	if (!tail) {
+		DCCP_CRIT("tail is null\n");
+		return ~0;
+	}
+
+	delta = timeval_delta(&tstamp, &tail->dccphrx_tstamp);
+	DCCP_BUG_ON(delta < 0);
+
+	rtt = delta * 4 / interval;
+	ccid3_pr_debug("%s(%p), approximated RTT to %dus\n",
+		       dccp_role(sk), sk, (int)rtt);
+
+	/*
+	 * 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 [RFC 3448, 6.3.1].
+	 */
+	if (rtt = 0) {			/* would result in divide-by-zero */
+		DCCP_WARN("RTT=0\n");
+		return ~0;
+	}
+
+	dccp_timestamp(sk, &tstamp);
+	delta = timeval_delta(&tstamp, &hcrx->ccid3hcrx_tstamp_last_feedback);
+	DCCP_BUG_ON(delta <= 0);
+
+	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 ~0;
+		}
+	}
+
+	fval = scaled_div(hcrx->ccid3hcrx_s, 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);
+
+	if (p = 0)
+		return ~0;
+	else
+		return 1000000 / p;
+}
+
+static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
+{
+	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
+	struct dccp_li_hist_entry *head;
+	u64 seq_temp;
+
+	if (list_empty(&hcrx->ccid3hcrx_li_hist)) {
+		if (!dccp_li_hist_interval_new(ccid3_li_hist,
+		   &hcrx->ccid3hcrx_li_hist, seq_loss, win_loss))
+			return;
+
+		head = list_entry(hcrx->ccid3hcrx_li_hist.next,
+		   struct dccp_li_hist_entry, dccplih_node);
+		head->dccplih_interval = ccid3_hc_rx_calc_first_li(sk);
+	} else {
+		struct dccp_li_hist_entry *entry;
+		struct list_head *tail;
+
+		head = list_entry(hcrx->ccid3hcrx_li_hist.next,
+		   struct dccp_li_hist_entry, dccplih_node);
+		/* FIXME win count check removed as was wrong */
+		/* should make this check with receive history */
+		/* and compare there as per section 10.2 of RFC4342 */
+
+		/* new loss event detected */
+		/* calculate last interval length */
+		seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss);
+		entry = dccp_li_hist_entry_new(ccid3_li_hist, GFP_ATOMIC);
+
+		if (entry = NULL) {
+			DCCP_BUG("out of memory - can not allocate entry");
+			return;
+		}
+
+		list_add(&entry->dccplih_node, &hcrx->ccid3hcrx_li_hist);
+
+		tail = hcrx->ccid3hcrx_li_hist.prev;
+		list_del(tail);
+		kmem_cache_free(ccid3_li_hist->dccplih_slab, tail);
+
+		/* Create the newest interval */
+		entry->dccplih_seqno = seq_loss;
+		entry->dccplih_interval = seq_temp;
+		entry->dccplih_win_count = win_loss;
+	}
+}
+
 static int ccid3_hc_rx_detect_loss(struct sock *sk,
 				    struct dccp_rx_hist_entry *packet)
 {
@@ -836,15 +985,8 @@ static int ccid3_hc_rx_detect_loss(struc
 	while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno)
 	   > TFRC_RECV_NUM_LATE_LOSS) {
 		loss = 1;
-		dccp_li_update_li(sk,
-				  &hcrx->ccid3hcrx_li_hist,
-				  &hcrx->ccid3hcrx_hist,
-				  &hcrx->ccid3hcrx_tstamp_last_feedback,
-				  hcrx->ccid3hcrx_s,
-				  hcrx->ccid3hcrx_bytes_recv,
-				  hcrx->ccid3hcrx_x_recv,
-				  hcrx->ccid3hcrx_seqno_nonloss,
-				  hcrx->ccid3hcrx_ccval_nonloss);
+		ccid3_hc_rx_update_li(sk, hcrx->ccid3hcrx_seqno_nonloss,
+		   hcrx->ccid3hcrx_ccval_nonloss);
 		tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss;
 		dccp_inc_seqno(&tmp_seqno);
 		hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno;
@@ -1003,7 +1145,7 @@ static void ccid3_hc_rx_exit(struct sock
 	dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
 
 	/* Empty loss interval history */
-	dccp_li_hist_purge(&hcrx->ccid3hcrx_li_hist);
+	dccp_li_hist_purge(ccid3_li_hist, &hcrx->ccid3hcrx_li_hist);
 }
 
 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
@@ -1087,12 +1229,19 @@ static __init int ccid3_module_init(void
 	if (ccid3_tx_hist = NULL)
 		goto out_free_rx;
 
+	ccid3_li_hist = dccp_li_hist_new("ccid3");
+	if (ccid3_li_hist = NULL)
+		goto out_free_tx;
+
 	rc = ccid_register(&ccid3);
 	if (rc != 0)
-		goto out_free_tx;
+		goto out_free_loss_interval_history;
 out:
 	return rc;
 
+out_free_loss_interval_history:
+	dccp_li_hist_delete(ccid3_li_hist);
+	ccid3_li_hist = NULL;
 out_free_tx:
 	dccp_tx_hist_delete(ccid3_tx_hist);
 	ccid3_tx_hist = NULL;
@@ -1115,6 +1264,10 @@ static __exit void ccid3_module_exit(voi
 		dccp_rx_hist_delete(ccid3_rx_hist);
 		ccid3_rx_hist = NULL;
 	}
+	if (ccid3_li_hist != NULL) {
+		dccp_li_hist_delete(ccid3_li_hist);
+		ccid3_li_hist = NULL;
+	}
 }
 module_exit(ccid3_module_exit);
 
net/dccp/ccids/lib/loss_interval.c +43 -195

273 lines not on this page · raw message

net/dccp/ccids/lib/loss_interval.h +35 -7

51 lines not on this page · raw message

#2 lore raw
In reply to Gerrit Renker
|  > [CCID3]: Revert code shifts
|  >
|  Don't totally agree with this approach but it is a hell of a lot
|  easier than reworking the patches I agree...
|  >

If there are any qualms I'd be happy to go over the patch again and discuss these. Below are the major differences between code reverted by this patch set and test tree.

Basically, yes, this is the easier (and maybe cleaner) alternative.

There is overlap between your and Arnaldo's work: I have just gathered all overlap into one patch and verified afterwards that this combination of above patch plus the other submitted patches doesn't introduce any other changes.

loss_interval.{c,h}:
==========
* the patch reverts the following removals
- struct dccp_li_hist (became global variable `dccp_li_cachep' in loss_interval.c) => the test tree uses exactly the same approach: static *tfrc_lh_slab => I have now changed the implementation in the test tree to also use __read_mostly This change is in the test-tree patch entitled "[TFRC]: Cache allocation of entries" and the inter-diff to before reads:
1531c1531
< +static struct kmem_cache *tfrc_lh_slab;
---
> +static struct kmem_cache *tfrc_lh_slab __read_mostly;

- dccp_li_hist_new()
=> also removed in test tree, due to the same approach of making slab local to dccp_tfrc_lib

- struct dccp_li_hist_entry (became local to loss_interval.c)
=> this could be done in the test tree, but I don't see the advantages at the moment

- dccp_li_hist_entry_new()
=> replaced by on-demand allocation in tfrc_lh_interval_add(), with low-level details hidden

- dccp_li_hist_interval_new()
=> integrated with tfrc_lh_interval_add(), same as with dccp_li_hist_entry_new()

- dccp_li_hist_entry_delete()
=> obsoleted by the use of ringbuffer, connection uses at most NINTERVAL+1=9 entries,
all cleanup is at connection end; no memory is required on lossless connections

* the patch reverts the following additions made by your and Arnaldos work:
- dccp_li_calc_first_li() => replaced by function pointer call (as discussed earlier on this list), this separates the TFRC / CCID3 interfaces
- dccp_li_update_li() => this has been rewritten into tfrc_lh_interval_add(), with much re-design

* the patch changes the following which stayed the same in your and Arnaldos work:
- dccp_li_hist_purge() => becomes tfrc_lh_cleanup()
- dccp_li_hist_calc_i_mean() => becomes tfrc_lh_update_i_mean() plus tfrc_lh_calc_i_mean()

- dccp_li_init() => becomes li_init()
- dccp_li_exit => becomes li_cleanup()

ccid3.c:
====
* removal of ccid3_li_hist is the same in the test tree
* ccid3_hc_rx_calc_first_li() stays in ccid3.c, but is rewritten into ccid3_first_li()
* ccid3_hc_rx_update_li() is also removed in the test tree from ccid3.c (cf. above)
* code that uses dccp_li_update_li() is removed in the test tree, due to use of tfrc_lh_interval_add()
* module init/exit code has been updated analogously in the test tree