TX history patches was: Re: Test tree patch inventory - update

Em Sat, Nov 17, 2007 at 03:42:52PM +0000, Gerrit Renker escreveu:

Hi Gerrit,

I reworked these two patches into this one below, please take a
look. I'll go thru the RX and loss events soon.

- Arnaldo

commit 866e2bc985b99a11622e8ed6ffd2bf2d161bed06

Author: Arnaldo Carvalho de Melo <[email protected]>
Date:   Thu Nov 22 17:49:59 2007 -0200

[TFRC]: Migrate TX history to singly-linked lis

This patch was based on another made by Gerrit Renker, his changelog was:

------------------------------------------------------
The patch set migrates TFRC TX history to a singly-linked list.

The details are:
* use of a consistent naming scheme (all TFRC functions now begin with `tfrc_');
* allocation and cleanup are taken care of internally;
* provision of a lookup function, which is used by the CCID TX infrastructure to determine the time a packet was sent (in turn used for RTT sampling);
* integration of the new interface with the present use in CCID3.
------------------------------------------------------

Simplifications I did:

. removing the tfrc_tx_hist_head that had a pointer to the list head and
another for the slabcache.
. No need for creating a slabcache for each CCID that wants to use the TFRC
tx history routines, create a single slabcache when the dccp_tfrc_lib module init routine is called.

index 964ec91..2668de8 100644
@@ -49,7 +49,6 @@ static int ccid3_debug;
 #define ccid3_pr_debug(format, a...)
 #endif
 
-static struct dccp_tx_hist *ccid3_tx_hist;
 static struct dccp_rx_hist *ccid3_rx_hist;
 
 /*

@@ -389,28 +388,18 @@ static void ccid3_hc_tx_packet_sent(struct sock *sk, int more,
 				    unsigned int len)
 {
 	struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
-	struct dccp_tx_hist_entry *packet;
 
 	ccid3_hc_tx_update_s(hctx, len);
 
-	packet = dccp_tx_hist_entry_new(ccid3_tx_hist, GFP_ATOMIC);
-	if (unlikely(packet = NULL)) {
+	if (tfrc_tx_hist_add(&hctx->ccid3hctx_hist, dccp_sk(sk)->dccps_gss))
 		DCCP_CRIT("packet history - out of memory!");
-		return;
-	}
-	dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, packet);
-
-	packet->dccphtx_tstamp = ktime_get_real();
-	packet->dccphtx_seqno  = dccp_sk(sk)->dccps_gss;
-	packet->dccphtx_rtt    = hctx->ccid3hctx_rtt;
-	packet->dccphtx_sent   = 1;
 }
 
 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
 {
 	struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
 	struct ccid3_options_received *opt_recv;
-	struct dccp_tx_hist_entry *packet;
+	struct tfrc_tx_hist_entry *packet;
 	ktime_t now;
 	unsigned long t_nfb;
 	u32 pinv, r_sample;

@@ -425,16 +414,19 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
 	switch (hctx->ccid3hctx_state) {
 	case TFRC_SSTATE_NO_FBACK:
 	case TFRC_SSTATE_FBACK:
-		/* get packet from history to look up t_recvdata */
-		packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
-					      DCCP_SKB_CB(skb)->dccpd_ack_seq);
-		if (unlikely(packet = NULL)) {
-			DCCP_WARN("%s(%p), seqno %llu(%s) doesn't exist "
-				  "in history!\n",  dccp_role(sk), sk,
-			    (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq,
-				dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
+		/* estimate RTT from history if ACK number is valid */
+		packet = tfrc_tx_hist_find_entry(hctx->ccid3hctx_hist,
+						 DCCP_SKB_CB(skb)->dccpd_ack_seq);
+		if (packet = NULL) {
+			DCCP_WARN("%s(%p): %s with bogus ACK-%llu\n", dccp_role(sk), sk,
+				  dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type),
+				  (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq);
 			return;
 		}
+		/*
+		 * Garbage-collect older (irrelevant) entries
+		 */
+		tfrc_tx_hist_purge(&packet->next);
 
 		/* Update receive rate in units of 64 * bytes/second */
 		hctx->ccid3hctx_x_recv = opt_recv->ccid3or_receive_rate;

@@ -451,7 +443,7 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
 		/*
 		 * Calculate new RTT sample and update moving average
 		 */
-		r_sample = dccp_sample_rtt(sk, ktime_us_delta(now, packet->dccphtx_tstamp));
+		r_sample = dccp_sample_rtt(sk, ktime_us_delta(now, packet->stamp));
 		hctx->ccid3hctx_rtt = tfrc_ewma(hctx->ccid3hctx_rtt, r_sample, 9);
 
 		if (hctx->ccid3hctx_state = TFRC_SSTATE_NO_FBACK) {

@@ -493,9 +485,6 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
 		/* unschedule no feedback timer */
 		sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
 
-		/* remove all packets older than the one acked from history */
-		dccp_tx_hist_purge_older(ccid3_tx_hist,
-					 &hctx->ccid3hctx_hist, packet);
 		/*
 		 * As we have calculated new ipi, delta, t_nom it is possible
 		 * that we now can send a packet, so wake up dccp_wait_for_ccid

@@ -598,7 +587,7 @@ static int ccid3_hc_tx_init(struct ccid *ccid, struct sock *sk)
 	struct ccid3_hc_tx_sock *hctx = ccid_priv(ccid);
 
 	hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
-	INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
+	hctx->ccid3hctx_hist = NULL;
 	setup_timer(&hctx->ccid3hctx_no_feedback_timer,
 			ccid3_hc_tx_no_feedback_timer, (unsigned long)sk);
 

@@ -612,8 +601,7 @@ static void ccid3_hc_tx_exit(struct sock *sk)
 	ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
 	sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
 
-	/* Empty packet history */
-	dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
+	tfrc_tx_hist_purge(&hctx->ccid3hctx_hist);
 }
 
 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)

@@ -1036,19 +1024,12 @@ static __init int ccid3_module_init(void)
 	if (ccid3_rx_hist = NULL)
 		goto out;
 
-	ccid3_tx_hist = dccp_tx_hist_new("ccid3");
-	if (ccid3_tx_hist = NULL)
-		goto out_free_rx;
-
 	rc = ccid_register(&ccid3);
 	if (rc != 0)
-		goto out_free_tx;
+		goto out_free_rx;
 out:
 	return rc;
 
-out_free_tx:
-	dccp_tx_hist_delete(ccid3_tx_hist);
-	ccid3_tx_hist = NULL;
 out_free_rx:
 	dccp_rx_hist_delete(ccid3_rx_hist);
 	ccid3_rx_hist = NULL;

@@ -1060,10 +1041,6 @@ static __exit void ccid3_module_exit(void)
 {
 	ccid_unregister(&ccid3);
 
-	if (ccid3_tx_hist != NULL) {
-		dccp_tx_hist_delete(ccid3_tx_hist);
-		ccid3_tx_hist = NULL;
-	}
 	if (ccid3_rx_hist != NULL) {
 		dccp_rx_hist_delete(ccid3_rx_hist);
 		ccid3_rx_hist = NULL;

index 36eca34..b842a7d 100644
@@ -40,6 +40,7 @@
 #include <linux/list.h>
 #include <linux/types.h>
 #include <linux/tfrc.h>
+#include "lib/packet_history.h"
 #include "../ccid.h"
 
 /* Two seconds as per RFC 3448 4.2 */

@@ -111,7 +112,7 @@ struct ccid3_hc_tx_sock {
 	ktime_t				ccid3hctx_t_ld;
 	ktime_t				ccid3hctx_t_nom;
 	u32				ccid3hctx_delta;
-	struct list_head		ccid3hctx_hist;
+	struct tfrc_tx_hist_entry	*ccid3hctx_hist;
 	struct ccid3_options_received	ccid3hctx_options_received;
 };
 

index 40ad428..ccd04a6 100644
@@ -277,7 +277,7 @@ void dccp_li_update_li(struct sock *sk,
 
 EXPORT_SYMBOL_GPL(dccp_li_update_li);
 
-static __init int dccp_li_init(void)
+int __init dccp_li_init(void)
 {
 	dccp_li_cachep = kmem_cache_create("dccp_li_hist",
 					   sizeof(struct dccp_li_hist_entry),

@@ -285,10 +285,10 @@ static __init int dccp_li_init(void)
 	return dccp_li_cachep = NULL ? -ENOBUFS : 0;
 }
 
-static __exit void dccp_li_exit(void)
+void dccp_li_exit(void)
 {
-	kmem_cache_destroy(dccp_li_cachep);
+	if (dccp_li_cachep != NULL) {
+		kmem_cache_destroy(dccp_li_cachep);
+		dccp_li_cachep = NULL;
+	}
 }
-
-module_init(dccp_li_init);
-module_exit(dccp_li_exit);

|         ------------------------------------------------------
|     The patch set migrates TFRC TX history to a singly-linked list.
|     
|     The details are:
|      * use of a consistent naming scheme (all TFRC functions now begin with `tfrc_');
|      * allocation and cleanup are taken care of internally;
|      * provision of a lookup function, which is used by the CCID TX infrastructure
|        to determine the time a packet was sent (in turn used for RTT sampling);
|      * integration of the new interface with the present use in CCID3.
|         ------------------------------------------------------
|     
|     Simplifications I did:
|     
|     . removing the tfrc_tx_hist_head that had a pointer to the list head and
|       another for the slabcache.
|     . No need for creating a slabcache for each CCID that wants to use the TFRC
|       tx history routines, create a single slabcache when the dccp_tfrc_lib module
|       init routine is called.
|     

These two above points are a good job and are useful. Well done. However, you have added other changes which are not in the above list, where I would like to make two suggestions.

Also did you test this code? The patch on which this is based has been subjected to some extensive regression-testing. I can't tell if it will perform as intended.

| --- a/net/dccp/ccids/ccid3.c
| +++ b/net/dccp/ccids/ccid3.c
|  static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
|  {
|  	struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
|  	struct ccid3_options_received *opt_recv;
| +	struct tfrc_tx_hist_entry *packet;
|  	ktime_t now;
|  	unsigned long t_nfb;
|  	u32 pinv, r_sample;
| @@ -425,16 +414,19 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
|  	switch (hctx->ccid3hctx_state) {
|  	case TFRC_SSTATE_NO_FBACK:
|  	case TFRC_SSTATE_FBACK:
| +		/* estimate RTT from history if ACK number is valid */
| +		packet = tfrc_tx_hist_find_entry(hctx->ccid3hctx_hist,
| +						 DCCP_SKB_CB(skb)->dccpd_ack_seq);
| +		if (packet = NULL) {
| +			DCCP_WARN("%s(%p): %s with bogus ACK-%llu\n", dccp_role(sk), sk,
| +				  dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type),
| +				  (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq);
|  			return;
|  		}
| +		/*
| +		 * Garbage-collect older (irrelevant) entries
| +		 */
| +		tfrc_tx_hist_purge(&packet->next);
|  
|  		/* Update receive rate in units of 64 * bytes/second */
|  		hctx->ccid3hctx_x_recv = opt_recv->ccid3or_receive_rate;
<snip>
|  		/*
|  		 * Calculate new RTT sample and update moving average
|  		 */
| +		r_sample = dccp_sample_rtt(sk, ktime_us_delta(now, packet->stamp));
|  		hctx->ccid3hctx_rtt = tfrc_ewma(hctx->ccid3hctx_rtt, r_sample, 9);
|  

Sorry but I don't like this at all.

All the low-level details of the packet_history interface are now again integrated into ccid3.c, so that ccid3.c ends up doing the job that packet_history can just as well do:

* first find the entry
* then purge all older entries
* then look into the packet entry to read the timestamp

CCID3 (and for that matter CCID4 also) use the TX history only for a single purpose - to look up the send time. If there was another method, the entire TX history could go.

The main intention of this patch set has been to separate more clearly between ccid3.c, loss_interval.c, and packet_history.c. If RTT measurement is done in the above way, then we don't gain much from the new patches. And other modules using tfrc_lib, such as CCID4, will have to perform the same manual steps all over again (i.e. code duplication).

Can you therefore please consider to keep the function tfrc_hist_when() from the original patch (or using a similar name).

That function only exposes what CCID3 is interested in - the send time - and takes care of the low-level detail. With regard to your new interface, it would look like

	int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
	{
	       struct tfrc_tx_hist_entry *entry = tfrc_tx_find_entry(head, ackno);

	       if (entry != NULL) {
		       *stamp = entry->stamp;
		       tfrc_tx_hist_purge(&entry->next);
		       return 1;
	       }
	       return 0;
	}

One of the main problems in the TFRC/CCID3 code has been (and to some extent still is) that the code is so deeply intertwined that it is almost impossible to keep functionality separate.

The comment below has the same background, but I suspect that you did this only as a temporary solution to make the module compile?

| --- a/net/dccp/ccids/lib/loss_interval.c
| +++ b/net/dccp/ccids/lib/loss_interval.c
|
| -static __init int dccp_li_init(void)
| +int __init dccp_li_init(void)

| -static __exit void dccp_li_exit(void)
| +void dccp_li_exit(void)
Here it is declared non-static so that packet_history can call it.

| --- a/net/dccp/ccids/lib/packet_history.c
| +++ b/net/dccp/ccids/lib/packet_history.c

| +extern int __init dccp_li_init(void);
| +extern void dccp_li_exit(void);
| +
| +static __init int packet_history_init(void)
| +{
| +	if (dccp_li_init() != 0)
| +		goto out;
<snip>
| +static __exit void packet_history_exit(void)
| +{
| +	if (tfrc_tx_hist != NULL) {
| +		kmem_cache_destroy(tfrc_tx_hist);
| +		tfrc_tx_hist = NULL;
| +	}
| +	dccp_li_exit();
| +}

The routine is called `packet_history_init()' and calls an initialisation routine in a different module (loss_interval.c). It is the same problem again that loss_interval and packet_history keep being intertwined.

A fix is available a few patches down the line; but more than likely you already noticed it. The patch introduces a separate source file tfrc_module.c which calls the individual initialisation routines of the source files that make up dccp_tfrc_lib:

tfrc_module_init()
- calls packet_history_init()
- calls loss_interval_init()
- does internal stuff

I think this is clearer, and it is extensible since then there is a dedicated file for dccp_tfrc_lib which can take up all the code which does not serve one of the particular purposes
* TFRC fixpoint lookup arithmetic (tfrc_equation.c)
* header includes for TFRC fixpoint arithmetic (tfrc.h)
* RX history and TX history interface (packet_history.{ch})
* book-keeping for loss intervals and computing loss event rates (loss_interval.{c,h})

Em Fri, Nov 23, 2007 at 10:49:29AM +0000, Gerrit Renker escreveu:

I performed testing, not exhaustive as the code should be equivalent to what you had done, or can you find, from code inspection, something suspicious?

Well we gain the fact that it is now uses a single linked list, that is what I tried to do in simplifying this patch.

I have no problem with this.

So we do:

1. convert the TX history to use a single linked list and use just one slabcache.

2. hide the internal TX history implementation details, since what the CCIDs are interested in is the time the packet being acknowledged or the extreme case where it couldn't find it in whatever data structure the TX history implementation uses.

Yes, see below.

Because both end up in the same kernel module, dccp_tfrc_lib.ko, so it doesn't matter where we put the module initialization routine, as long as it calls what each part of the lib wants to be called at init time.

Yes, this is clearer and noticed it, will get to that.

Its just that when simplifying the TX history by removing the need for a per CCID cache since the size of the object is the same for all clients, I needed to, at module init time, to create the slab cache, and to keep the patch as small as possible, I decided to use one of the existing files in net/dccp/ccids/lib/.

- Arnaldo

| > Also did you test this code? The patch on which this is based has been
| > subjected to some extensive regression-testing. I can't tell if it will
| > perform as intended.
| 
| I performed testing, not exhaustive as the code should be equivalent to
| what you had done, or can you find, from code inspection, something
| suspicious?
|  

Probably not - the code looks correct. I am probably paranoid, but after some bad experiences I test everything I do even if the change is a trivial one.

| > The main intention of this patch set has been to separate more clearly between ccid3.c,
| > loss_interval.c, and packet_history.c. If RTT measurement is done in the above way, then
| > we don't gain much from the new patches.
| 
| Well we gain the fact that it is now uses a single linked list, that is
| what I tried to do in simplifying this patch.
| 

Sorry I think you got me wrong. You have done a great job in making this patch even simpler and I fully agree with that -- the general idea is that with this simplification it is much better now. I think I was just being picky about details.

| > 	int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
| > 	{
| > 	       struct tfrc_tx_hist_entry *entry = tfrc_tx_find_entry(head, ackno);
| > 
| > 	       if (entry != NULL) {
| > 		       *stamp = entry->stamp;
| > 		       tfrc_tx_hist_purge(&entry->next);
| > 		       return 1;
| > 	       }
| > 	       return 0;
| > 	}
| > 
| > One of the main problems in the TFRC/CCID3 code has been (and to some extent still is)
| > that the code is so deeply intertwined that it is almost impossible to keep functionality separate.
| 
| I have no problem with this.
| 
| So we do:
| 
| 1. convert the TX history to use a single linked list and use
|    just one slabcache.
| 
| 2. hide the internal TX history implementation details, since
|    what the CCIDs are interested in is the time the packet
|    being acknowledged or the extreme case where it couldn't find it
|    in whatever data structure the TX history implementation uses.
|

Point (1) is your addition to the patch and as said, I really like this. With the second point I also agree, and also thought this over: I had a problem with a missing RTT value somewhere else (retransmission of Close/CloseReq). If only we had a way of performing RTT measurement in the main module, the entire TX list could go. But until then it would be great to just hide away the TX history implementation details as you suggest.

| > The comment below has the same background, but I suspect that you did
| > this only as a temporary solution to make the module compile?
| 
| Yes, see below.
|  

I almost expected this so please forget the comment.