[PATCH 0/4] Adds implementation of TFRC-SP sender side into the DCCP test tree

[PATCH 0/4] Adds implementation of TFRC-SP sender side into the DCCP test tree

[Ivo Calado]

These patches adds implementation of TFRC-SP at the sender side, and are targeted at the DCCP branch.



Patch #1: Adds random ect generation to tfrc-sp sender side
Patch #2: Implement function that allows to keep track of packets sent in last 2 rtt
Patch #3: Implement dropped packets option
Patch #4: Implement loss intervals option


--
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab -
http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center -
http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Quidquid latine dictum sit, altum viditur.

[PATCH 1/4] Adds random ect generation to tfrc-sp sender side

[Ivo Calado]

Adds random ect generation to tfrc-sp sender side. Before sending the packet, TFRC-SP chooses randomly
one ect codepoint, returns it and register at the ect history list.

Changes:
 - Creates tfrc_sp_get_random_ect, that uses random.h to choose one ect codepoint
 - Defines tfrc_tx_li_data, that stores data parsed from options loss intervals and dropped packets, and ecn nonce history
 - Defines tfrc_ecn_echo_sum_entry, type of entries of ecn nonce history list
 - Adds memory manage routines and code to these structures

Signed-off-by: Ivo Calado <ivocalado@embedded.ufcg.edu.br>
Signed-off-by: Erivaldo Xavier <desadoc@gmail.com>
Signed-off-by: Leandro Sales <leandroal@gmail.com>

Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c
===================================================================
--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.c	2009-10-08 22:59:20.526408512 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c	2009-10-08 22:59:26.926501680 -0300
@@ -15,6 +15,7 @@
 
 static struct kmem_cache  *tfrc_lh_slab  __read_mostly;
 static struct kmem_cache  *tfrc_ld_slab  __read_mostly;
+static struct kmem_cache  *tfrc_ecn_echo_sum_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 };
 
@@ -84,6 +85,48 @@
 }
 
 /*
+ * tfrc_sp_get_random_ect  -  return random ect codepoint
+ * li_data:		data where to register ect sent
+ * seqn:		packet's sequence number
+ */
+int tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn)
+{
+	int ect;
+	struct tfrc_ecn_echo_sum_entry *sum;
+
+	/* TODO: implement random ect*/
+	ect = INET_ECN_ECT_0;
+
+	sum = kmem_cache_alloc(tfrc_ecn_echo_sum_slab, GFP_ATOMIC);
+
+	sum->previous = li_data->ecn_sums_head;
+	sum->ecn_echo_sum = (sum->previous->ecn_echo_sum) ? !ect : ect;
+	sum->seq_num = seqn;
+
+	li_data->ecn_sums_head = sum;
+
+	return ect;
+}
+
+/*
+ * tfrc_sp_tx_ld_cleanup  -  free all entries
+ * echo_sums_data:		head of the list
+ */
+void tfrc_sp_tx_ld_cleanup(struct tfrc_ecn_echo_sum_entry **echo_sums_data)
+{
+	struct tfrc_ecn_echo_sum_entry *e, *previous;
+	e = *echo_sums_data;
+
+	while (e != NULL) {
+		previous = e->previous;
+		kmem_cache_free(tfrc_ecn_echo_sum_slab, e);
+		e = previous;
+	}
+
+	*echo_sums_data = NULL;
+}
+
+/*
  * Allocation routine for new entries of loss interval data
  */
 static struct tfrc_loss_data_entry *tfrc_ld_add_new(struct tfrc_loss_data *ld)
@@ -493,8 +536,13 @@
 	tfrc_ld_slab = kmem_cache_create("tfrc_sp_li_data",
 					 sizeof(struct tfrc_loss_data_entry), 0,
 					 SLAB_HWCACHE_ALIGN, NULL);
-
-	if ((tfrc_lh_slab != NULL) && (tfrc_ld_slab != NULL))
+	tfrc_ecn_echo_sum_slab = kmem_cache_create("tfrc_sp_ecn_echo_sum",
+				sizeof(struct tfrc_ecn_echo_sum_entry), 0,
+						SLAB_HWCACHE_ALIGN, NULL);
+
+	if ((tfrc_lh_slab != NULL) &&
+	    (tfrc_ld_slab != NULL) &&
+	    (tfrc_ecn_echo_sum_slab != NULL))
 		return 0;
 
 	if (tfrc_lh_slab != NULL) {
@@ -507,6 +555,11 @@
 		tfrc_ld_slab = NULL;
 	}
 
+	if (tfrc_ecn_echo_sum_slab != NULL) {
+		kmem_cache_destroy(tfrc_ecn_echo_sum_slab);
+		tfrc_ecn_echo_sum_slab = NULL;
+	}
+
 	return -ENOBUFS;
 }
 
@@ -521,4 +574,9 @@
 		kmem_cache_destroy(tfrc_ld_slab);
 		tfrc_ld_slab = NULL;
 	}
+
+	if (tfrc_ecn_echo_sum_slab != NULL) {
+		kmem_cache_destroy(tfrc_ecn_echo_sum_slab);
+		tfrc_ecn_echo_sum_slab = NULL;
+	}
 }
Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h
===================================================================
--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.h	2009-10-08 22:59:20.526408512 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h	2009-10-08 22:59:26.926501680 -0300
@@ -128,6 +128,31 @@
 	memset(ld, 0, sizeof(*ld));
 }
 
+/*
+ * tfrc_ecn_echo_sum_entry  -  store sent ecn codepoint info
+ * ecn_echo_sum:		ecn echo sum up to that packet
+ * seq_num:			sequence number of packet
+ * previous:			previous sent packet info
+ */
+struct tfrc_ecn_echo_sum_entry {
+	u8				ecn_echo_sum:1;
+	u64				seq_num:48;
+	struct tfrc_ecn_echo_sum_entry	*previous;
+};
+
+/*
+ * tfrc_tx_li_data  -  data about sent ecn and parsed options
+ * ecn_sums_head:		ecn data list
+ * seq_num:			sequence number of packet
+ * previous:			previous sent packet info
+ */
+struct tfrc_tx_li_data {
+	struct tfrc_ecn_echo_sum_entry	*ecn_sums_head;
+	u32				dropped_packets_data[1 + 9];
+	u32				loss_interval_data[1 + 9];
+	u8				skip_length;
+};
+
 struct tfrc_rx_hist;
 
 extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *,
@@ -143,6 +168,8 @@
 extern void tfrc_sp_lh_cleanup(struct tfrc_loss_hist *lh);
 extern void tfrc_sp_ld_cleanup(struct tfrc_loss_data *ld);
 extern void tfrc_sp_ld_prepare_data(u8 loss_count, struct tfrc_loss_data *ld);
+extern int  tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn);
+extern void tfrc_sp_tx_ld_cleanup(struct tfrc_ecn_echo_sum_entry **);
 
 #endif /* _DCCP_LI_HIST_SP_ */
 
Index: dccp_tree_work03/net/dccp/ccids/lib/tfrc_ccids_sp.h
===================================================================
--- dccp_tree_work03.orig/net/dccp/ccids/lib/tfrc_ccids_sp.h	2009-10-08 22:59:20.526408512 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/tfrc_ccids_sp.h	2009-10-08 22:59:26.926501680 -0300
@@ -85,6 +85,7 @@
 	ktime_t				t_ld;
 	ktime_t				t_nom;
 	struct tfrc_tx_hist_entry	*hist;
+	struct tfrc_tx_li_data 		li_data;
 };
 
 static inline struct tfrc_hc_tx_sock *tfrc_hc_tx_sk(const struct sock *sk)

Re: [PATCH 1/4] Adds random ect generation to tfrc-sp sender side

[Gerrit Renker]

| Adds random ect generation to tfrc-sp sender side.

I thought about this and found several reasons why it would be better to
defer ECN Nonce sums to a later implementation.

 1) At the moment the code always sets ECT(0). Even if it would
    alternate ECT(0) and ECT(1), this would later be overwritten by ECT(0)
    in dccp_msghdr_parse(). Ok, this could be fixed, but the real problem
    is that the underlying machinery does not support ECN nonces, since

    * ECN / DiffServ information is in two separate places of the
      inet_sock (u8 `tos' field and u8 `tclass' field of ipv6_pinfo);

    * the ECN driver sits in include/net/inet_ecn.h as
      #define INET_ECN_xmit(sk) do { inet_sk(sk)->tos |= INET_ECN_ECT_0; } while (0)

    * hence this would need to be revised and the best way to make an
      acceptable suggestion would be a coded proof of concept that 
      changing the underlying implementation does have benefits.

    On the receiver side the situation is the same. The function
    tfrc_sp_check_ecn_sum(), introduced in Patch 2/4 of the TFRC-SP sender
    implementation is only referenced in Patch 2/2 of the CCID-4 set, where
    it ends, without side effect in "TODO: consider ecn sum test fail".

    That is, at the moment both the sender and receiver side of the ECN Nonce
    sum verification are placeholders which currently have no effect.


 2) As far as I can see the ECN Nonce is an optimisation, an

      "optional addition to Explicit Congestion Notification [RFC3168]
       improving its robustness against malicious or accidental
       concealment of marked packets [...]" (from the abstract)

    Hence if at all, we would only have a benefit of adding the ECN Nonce
    verification on top of an already verified implementation.

 3) Starting an implementation throws up further questions that need to
    be addressed, both the basis and the extension need to be verified.

I would like to suggest to implement the basis, that is CCID-4 with ECN
(using plain ECT(0)), test with that until it works satisfactorily, and
then continue adding measures such as the ECN Nonce verification.

Nothing is lost, once we are at this stage we can return to this set of
initial patches and revise the situation based on the insights gained 
with ECT(0) experience.

In summary, I would like to suggest to remove the ECN verification for
the moment and focus on the "basic" issues first.

Would you be ok with that?



Appendix
--------
| +int tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn)
| +{
| +	int ect;
| +	struct tfrc_ecn_echo_sum_entry *sum;
| +
| +	/* TODO: implement random ect*/
| +	ect = INET_ECN_ECT_0;
| +
| +	sum = kmem_cache_alloc(tfrc_ecn_echo_sum_slab, GFP_ATOMIC);

For a later implementation, there should be protection against NULL, e.g.
        if (sum == NULL) {
	   DCCP_CRIT("Problem here ...");
	   return 0;
	}
| +
| +	sum->previous = li_data->ecn_sums_head;
| +	sum->ecn_echo_sum = (sum->previous->ecn_echo_sum) ? !ect : ect;

(Also for later) I wonder how to do the sums, with RFC 3168
ECT(0) = 0x2 => !0x2 = 0
ECT(1) = 0x1 => !0x1 = 0

>From the addition table in RFC 3540, section 2,
ECT(0) + ECT(0) = 0
ECT(0) + ECT(1) = 1
ECT(1) + ECT(1) = 0

One way could be
        sum->ecn_echo_sum ^= (ect == INET_ECN_ECT_1);

Re: [PATCH 1/4] Adds random ect generation to tfrc-sp sender side

[Ivo Calado]

On Mon, Oct 19, 2009 at 2:23 AM, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> | Adds random ect generation to tfrc-sp sender side.
>
> I thought about this and found several reasons why it would be better to
> defer ECN Nonce sums to a later implementation.
>
>  1) At the moment the code always sets ECT(0). Even if it would
>    alternate ECT(0) and ECT(1), this would later be overwritten by ECT(0)
>    in dccp_msghdr_parse(). Ok, this could be fixed, but the real problem
>    is that the underlying machinery does not support ECN nonces, since
>
>    * ECN / DiffServ information is in two separate places of the
>      inet_sock (u8 `tos' field and u8 `tclass' field of ipv6_pinfo);
>
>    * the ECN driver sits in include/net/inet_ecn.h as
>      #define INET_ECN_xmit(sk) do { inet_sk(sk)->tos |= INET_ECN_ECT_0; } while (0)
>
>    * hence this would need to be revised and the best way to make an
>      acceptable suggestion would be a coded proof of concept that
>      changing the underlying implementation does have benefits.
>
>    On the receiver side the situation is the same. The function
>    tfrc_sp_check_ecn_sum(), introduced in Patch 2/4 of the TFRC-SP sender
>    implementation is only referenced in Patch 2/2 of the CCID-4 set, where
>    it ends, without side effect in "TODO: consider ecn sum test fail".
>
>    That is, at the moment both the sender and receiver side of the ECN Nonce
>    sum verification are placeholders which currently have no effect.
>

Okay, then the implementation would be useless now.

>
>  2) As far as I can see the ECN Nonce is an optimisation, an
>
>      "optional addition to Explicit Congestion Notification [RFC3168]
>       improving its robustness against malicious or accidental
>       concealment of marked packets [...]" (from the abstract)
>
>    Hence if at all, we would only have a benefit of adding the ECN Nonce
>    verification on top of an already verified implementation.
>

Yes, not priority at all. And you're right, no benefit.

>  3) Starting an implementation throws up further questions that need to
>    be addressed, both the basis and the extension need to be verified.
>
> I would like to suggest to implement the basis, that is CCID-4 with ECN
> (using plain ECT(0)), test with that until it works satisfactorily, and
> then continue adding measures such as the ECN Nonce verification.
>

Okay. But, when would be good to at least include random ECT
generation? When DCCP ECN code will get fixed? Is there any work on
this?

> Nothing is lost, once we are at this stage we can return to this set of
> initial patches and revise the situation based on the insights gained
> with ECT(0) experience.
>
> In summary, I would like to suggest to remove the ECN verification for
> the moment and focus on the "basic" issues first.
>
> Would you be ok with that?
>

Yes, we'll keep the ECN verification code here at our git until the
scenario is ready.

>
>
> Appendix
> --------
> | +int tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn)
> | +{
> | +     int ect;
> | +     struct tfrc_ecn_echo_sum_entry *sum;
> | +
> | +     /* TODO: implement random ect*/
> | +     ect = INET_ECN_ECT_0;
> | +
> | +     sum = kmem_cache_alloc(tfrc_ecn_echo_sum_slab, GFP_ATOMIC);
>
> For a later implementation, there should be protection against NULL, e.g.
>        if (sum == NULL) {
>           DCCP_CRIT("Problem here ...");
>           return 0;
>        }
> | +
> | +     sum->previous = li_data->ecn_sums_head;
> | +     sum->ecn_echo_sum = (sum->previous->ecn_echo_sum) ? !ect : ect;
>

Thanks, i forgot that.

> (Also for later) I wonder how to do the sums, with RFC 3168
> ECT(0) = 0x2 => !0x2 = 0
> ECT(1) = 0x1 => !0x1 = 0
>

I don't understand. Can you try to explain it? Or cite RFC section
that address it?

> From the addition table in RFC 3540, section 2,
> ECT(0) + ECT(0) = 0
> ECT(0) + ECT(1) = 1
> ECT(1) + ECT(1) = 0
>
> One way could be
>        sum->ecn_echo_sum ^= (ect == INET_ECN_ECT_1);

Ok.




-- 
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab - http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center - http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Quidquid latine dictum sit, altum viditur.

Re: [PATCH 1/4] Adds random ect generation to tfrc-sp sender side

[Gerrit Renker]

| >    That is, at the moment both the sender and receiver side of the ECN Nonce
| >    sum verification are placeholders which currently have no effect.
| >
| 
| Okay, then the implementation would be useless now.
I was not suggesting to throw away the patches, we can keep them for
later use.

They are a good starting basis once it makes sense to work with ECN.
Or how can we test ECN if we are not sure that the other parts work
as they are supposed to?

| >  3) Starting an implementation throws up further questions that need to
| >    be addressed, both the basis and the extension need to be verified.
| >
| > I would like to suggest to implement the basis, that is CCID-4 with ECN
| > (using plain ECT(0)), test with that until it works satisfactorily, and
| > then continue adding measures such as the ECN Nonce verification.
| >
| 
| Okay. But, when would be good to at least include random ECT
| generation? When DCCP ECN code will get fixed? Is there any work on
| this?
| 
I asked this on netdev earlier, there was not much enthusiasm.

The issue is that ECN belongs both to the network and the transport layer.
This network layer is in inet_ecn.h, outside of DCCP.

I believe that the changes would not be too hard to do, by changing the
macros. But it requires working with the people on netdev, in particular
to ensure it does not break something in the TCP/SCTP subsystems (both
also use ECN, and then there are also raw sockets).

I also have an interest in resolving this, due to the ugliness at the
moment for enabling ECN on IPv6.

RFC 2884, written by one of the Linux ECN developers, describes early
IPv4 ECN evaluation. It seems that initially it was planned to only 
support ECN over Ipv4, parts of the code may be still from that time.

We can pursue this in parallel to the other issues. Ideally this would be
resolved at the time the other parts of CCID-4 are ready for testing.

| > In summary, I would like to suggest to remove the ECN verification for
| > the moment and focus on the "basic" issues first.
| >
| > Would you be ok with that?
| >
| 
| Yes, we'll keep the ECN verification code here at our git until the
| scenario is ready.
| 
I was going to suggest to put them onto a webpage, such as yours, or on 
www.erg.abdn.ac.uk/users/gerrit/dccp there is also still some space.

Can you please elaborate how to keep your git tree and the one on
eden-feed synchronized? At the moment I have not made any changes other
than the ones I emailed you about. Is there a way of keeping both trees
in synch without running into versioning difficulties?

(The simplest way I can think of is to keep the patches in a separate
 set, or to spawn a subtree which contains the ECN patches on top of the
 CCID-4 tree.)


| > (Also for later) I wonder how to do the sums, with RFC 3168
| > ECT(0) = 0x2 => !0x2 = 0
| > ECT(1) = 0x1 => !0x1 = 0
| >
| 
| I don't understand. Can you try to explain it? Or cite RFC section
| that address it?
 
The values are from figure 1, page 7, the expressions evaluate both as 0:

void main(void)
{
	printf("!0x2 = %d, !0x1 = %d\n", !0x2, !0x1);
}

Re: [PATCH 1/4] Adds random ect generation to tfrc-sp sender side

[Ivo Calado]

On Mon, Oct 26, 2009 at 4:55 AM, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> | >    That is, at the moment both the sender and receiver side of the ECN Nonce
> | >    sum verification are placeholders which currently have no effect.
> | >
> |
> | Okay, then the implementation would be useless now.
> I was not suggesting to throw away the patches, we can keep them for
> later use.
>
> They are a good starting basis once it makes sense to work with ECN.
> Or how can we test ECN if we are not sure that the other parts work
> as they are supposed to?
>

Okay, we'll keep the patches.

> | >  3) Starting an implementation throws up further questions that need to
> | >    be addressed, both the basis and the extension need to be verified.
> | >
> | > I would like to suggest to implement the basis, that is CCID-4 with ECN
> | > (using plain ECT(0)), test with that until it works satisfactorily, and
> | > then continue adding measures such as the ECN Nonce verification.
> | >
> |
> | Okay. But, when would be good to at least include random ECT
> | generation? When DCCP ECN code will get fixed? Is there any work on
> | this?
> |
> I asked this on netdev earlier, there was not much enthusiasm.
>
> The issue is that ECN belongs both to the network and the transport layer.
> This network layer is in inet_ecn.h, outside of DCCP.
>
> I believe that the changes would not be too hard to do, by changing the
> macros. But it requires working with the people on netdev, in particular
> to ensure it does not break something in the TCP/SCTP subsystems (both
> also use ECN, and then there are also raw sockets).
>
> I also have an interest in resolving this, due to the ugliness at the
> moment for enabling ECN on IPv6.
>
> RFC 2884, written by one of the Linux ECN developers, describes early
> IPv4 ECN evaluation. It seems that initially it was planned to only
> support ECN over Ipv4, parts of the code may be still from that time.
>
> We can pursue this in parallel to the other issues. Ideally this would be
> resolved at the time the other parts of CCID-4 are ready for testing.
>

Ok.

> | > In summary, I would like to suggest to remove the ECN verification for
> | > the moment and focus on the "basic" issues first.
> | >
> | > Would you be ok with that?
> | >
> |
> | Yes, we'll keep the ECN verification code here at our git until the
> | scenario is ready.
> |
> I was going to suggest to put them onto a webpage, such as yours, or on
> www.erg.abdn.ac.uk/users/gerrit/dccp there is also still some space.
>
> Can you please elaborate how to keep your git tree and the one on
> eden-feed synchronized? At the moment I have not made any changes other
> than the ones I emailed you about. Is there a way of keeping both trees
> in synch without running into versioning difficulties?
>
> (The simplest way I can think of is to keep the patches in a separate
>  set, or to spawn a subtree which contains the ECN patches on top of the
>  CCID-4 tree.)
>

Ok, we'll put the patches at our webpage. And about the git, I can't
think a better way too.

>
> | > (Also for later) I wonder how to do the sums, with RFC 3168
> | > ECT(0) = 0x2 => !0x2 = 0
> | > ECT(1) = 0x1 => !0x1 = 0
> | >
> |
> | I don't understand. Can you try to explain it? Or cite RFC section
> | that address it?
>
> The values are from figure 1, page 7, the expressions evaluate both as 0:
>
> void main(void)
> {
>        printf("!0x2 = %d, !0x1 = %d\n", !0x2, !0x1);
> }

Thanks.



-- 
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab - http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center - http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Putt's Law:
       Technology is dominated by two types of people:
               Those who understand what they do not manage.
               Those who manage what they do not understand.

[PATCH 3/4] Implement dropped packets option

[Ivo Calado]

Implement dropped packets option. First we parse the received option and store the data, then we check the ecn sum along
the intervals described. The last step calcs 'p' from the option data and only suceeds if loss interval data was parsed before
and is ready to be consumed.

Changes:
 - Adds tfrc_sp_check_ecn_sum, that checks ecn in the received option
 - Adds tfrc_sp_p_from_loss_intervals_opt, do 'p' calc from parsed and stored option data
 - Adds tfrc_sp_parse_dropped_packets_opt, that do the parsing of received option, storing data

Signed-off-by: Ivo Calado <ivocalado@embedded.ufcg.edu.br>
Signed-off-by: Erivaldo Xavier <desadoc@gmail.com>
Signed-off-by: Leandro Sales <leandroal@gmail.com>

Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c
===================================================================
--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.c	2009-10-08 22:59:26.926501680 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c	2009-10-08 22:59:38.114908156 -0300
@@ -350,6 +350,206 @@
 		h->ecn_nonce_sum = !h->ecn_nonce_sum;
 }
 
+/*
+ * tfrc_sp_check_ecn_sum  -  check received ecn sum parsed from
+ *			     loss interval option
+ * li_data:		data parsed from options
+ * optval:		data from option
+ * optlen:		option data length
+ * skb:		last received packet
+ */
+bool tfrc_sp_check_ecn_sum(struct tfrc_tx_li_data *li_data, u8 *optval,
+			   u8 optlen, struct sk_buff *skb)
+{
+	u8 skip_length;
+	u32 data_length;
+	u8 sum0, sum1, li_sum;
+	struct tfrc_ecn_echo_sum_entry *entry;
+	u64 seqn;
+
+	if ((optlen < 10) || ((optlen - 1)%3 != 0))
+		return false;
+
+	if (li_data == NULL)
+		return true;
+
+	entry = li_data->ecn_sums_head;
+
+	if (entry == NULL)
+		return true;
+
+	seqn = dccp_hdr_ack_seq(skb);
+
+	while (entry->seq_num != seqn) {
+		entry = entry->previous;
+
+		if (entry == NULL)
+			return true;
+	}
+
+	skip_length = *optval;
+	optval++;
+	optlen--;
+
+	while (skip_length--) {
+		entry = entry->previous;
+
+		if (entry == NULL)
+			return false;
+	}
+
+	optval += 3;
+	optlen -= 3;
+
+	do {
+		sum0 = entry->ecn_echo_sum;
+
+		li_sum = (*((u32 *)optval)&0x80000000) ? 1 : 0;
+
+		optval += 3;
+		optlen -= 3;
+
+		data_length = ntohl((*((u32 *)optval) & 0xFFFFFF00) >> 8);
+
+		while (--data_length) {
+			entry = entry->previous;
+
+			if (entry == NULL)
+				return true;
+		}
+
+		sum1 = entry->ecn_echo_sum;
+
+		if (((sum0+sum1) & 0x1) != li_sum)
+			return false;
+
+		optval += 6;
+		optlen -= 6;
+
+	} while (optlen >= 9);
+
+	if (entry != NULL)
+		tfrc_sp_tx_ld_cleanup(&entry->previous);
+
+	return true;
+}
+
+static struct tfrc_tx_hist_entry*
+	tfrc_sp_seek_tx_entry(struct tfrc_tx_hist_entry *head,
+			      u64 seqno, u32 backward)
+{
+	if (head == NULL)
+		return NULL;
+
+	while (head->seqno != seqno) {
+		head = head->next;
+
+		if (head == NULL)
+			return NULL;
+	}
+
+	while (backward-- > 0) {
+		head = head->next;
+
+		if (head == NULL)
+			return NULL;
+	}
+
+	return head;
+}
+
+/*
+ * tfrc_sp_p_from_loss_intervals_opt  -  calcs p from loss interval option
+ * li_data:		data parsed from options
+ * head:		contains ccval info
+ * curr_ccval:		current ccval
+ * seqno:		last acked seqno
+ */
+u32 tfrc_sp_p_from_loss_intervals_opt(struct tfrc_tx_li_data *li_data,
+				      struct tfrc_tx_hist_entry *head,
+				      u8 curr_ccval, u64 seqno)
+{
+	int i, k;
+	u8 ccval;
+	u32 i_i, i_tot0, i_tot1, w_tot, i_totl, losses, mean;
+	i_tot0 = i_tot1 = w_tot = i_totl = 0;
+
+	if (li_data->loss_interval_data[0] == 0)
+		return 0;
+
+	if (li_data->loss_interval_data[0] < li_data->dropped_packets_data[0])
+		return 0;
+
+	k = li_data->loss_interval_data[0];
+
+	for (i = 1; i <= k; i++) {
+		i_i = li_data->loss_interval_data[i];
+		i_totl += i_i;
+		ccval = tfrc_sp_seek_tx_entry(head, seqno, i_totl - 1)->ccval;
+
+		if (SUB16(curr_ccval, ccval) <= 8) {
+			losses = li_data->dropped_packets_data[i];
+
+			if (losses > 0)
+				i_i = div64_u64(i_i, losses);
+		}
+
+		if (i != k) {
+			i_tot0 += i_i * tfrc_lh_weights[i-1];
+			w_tot  += tfrc_lh_weights[i-1];
+		}
+
+		if (i > 1)
+			i_tot1 += i_i * tfrc_lh_weights[i-2];
+	}
+
+	ccval = tfrc_sp_seek_tx_entry(head, seqno,
+			li_data->loss_interval_data[1] - 1)->ccval;
+
+	if (SUB16(curr_ccval, ccval) > 8)
+		mean = max(i_tot0, i_tot1) / w_tot;
+	else
+		mean = i_tot1 / w_tot;
+
+	return tfrc_sp_invert_loss_event_rate(mean);
+
+	return 0;
+}
+
+/*
+ * tfrc_sp_parse_dropped_packets_opt  -  parses received dropped packets option
+ * li_data:		used to store parsed data
+ * optval:		option data
+ * optlen:		option length
+ */
+void tfrc_sp_parse_dropped_packets_opt(struct tfrc_tx_li_data *li_data,
+				       u8 *optval, u8 optlen)
+{
+	u8 pos;
+	u32 dropped;
+
+	if ((optlen%3) != 0) {
+		li_data->dropped_packets_data[0] = 0;
+		return;
+	}
+
+	pos = 0;
+
+	while (pos < optlen) {
+		dropped = ntohl(((*((u32 *)(optval + pos))) & 0xFFFFFF00) >> 8);
+		li_data->dropped_packets_data[1 + (pos/3)] = dropped;
+
+		if ((pos/3) == 9) {
+			li_data->dropped_packets_data[0] = 9;
+			return;
+		}
+
+		pos += 3;
+	}
+
+	li_data->dropped_packets_data[0] = optlen/3;
+}
+
 static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8 curr_ccval)
 {
 	u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
@@ -400,7 +600,10 @@
 	if (cur == NULL)			/* not initialised */
 		return;
 
-	/* FIXME: should probably also count non-data packets (RFC 4342, 6.1) */
+	/*
+	 * FIXME: should probably also count non-data packets
+	 * (RFC 4342, 6.1)
+	 */
 	if (!dccp_data_packet(skb))
 		return;
 
Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h
===================================================================
--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.h	2009-10-08 22:59:26.926501680 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h	2009-10-08 22:59:38.114908156 -0300
@@ -169,6 +169,14 @@
 extern void tfrc_sp_ld_cleanup(struct tfrc_loss_data *ld);
 extern void tfrc_sp_ld_prepare_data(u8 loss_count, struct tfrc_loss_data *ld);
 extern int  tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn);
+extern bool tfrc_sp_check_ecn_sum(struct tfrc_tx_li_data *li_data, u8 *optval,
+				  u8 optlen, struct sk_buff *skb);
+struct tfrc_tx_hist_entry;
+extern u32 tfrc_sp_p_from_loss_intervals_opt(struct tfrc_tx_li_data *li_data,
+					     struct tfrc_tx_hist_entry *head,
+					     u8 curr_ccval, u64 seqno);
+extern void tfrc_sp_parse_dropped_packets_opt(struct tfrc_tx_li_data *li_data,
+					      u8 *optval, u8 optlen);
 extern void tfrc_sp_tx_ld_cleanup(struct tfrc_ecn_echo_sum_entry **);
 
 #endif /* _DCCP_LI_HIST_SP_ */

Re: [PATCH 3/4] Implement dropped packets option

[Gerrit Renker]

| +static struct tfrc_tx_hist_entry*
| +	tfrc_sp_seek_tx_entry(struct tfrc_tx_hist_entry *head,
| +			      u64 seqno, u32 backward)
| +{
| +	if (head == NULL)
| +		return NULL;
| +
| +	while (head->seqno != seqno) {
| +		head = head->next;
| +
| +		if (head == NULL)
| +			return NULL;
| +	}
| +
| +	while (backward-- > 0) {
| +		head = head->next;
| +
| +		if (head == NULL)
| +			return NULL;
| +	}
| +
| +	return head;
| +}
| +
| +/*
| + * tfrc_sp_p_from_loss_intervals_opt  -  calcs p from loss interval option
| + * li_data:		data parsed from options
| + * head:		contains ccval info
| + * curr_ccval:		current ccval
| + * seqno:		last acked seqno
| + */
| +u32 tfrc_sp_p_from_loss_intervals_opt(struct tfrc_tx_li_data *li_data,
| +				      struct tfrc_tx_hist_entry *head,
| +				      u8 curr_ccval, u64 seqno)
| +{
<snip>
| +
| +	for (i = 1; i <= k; i++) {
| +		i_i = li_data->loss_interval_data[i];
| +		i_totl += i_i;
| +		ccval = tfrc_sp_seek_tx_entry(head, seqno, i_totl - 1)->ccval;

tfrc_sp_seek_tx_entry() can return NULL (as per above implementation). Then this
will crash/panic.

<snip>
| +
| +		if (i > 1)
| +			i_tot1 += i_i * tfrc_lh_weights[i-2];
| +	}
| +
| +	ccval = tfrc_sp_seek_tx_entry(head, seqno,
| +			li_data->loss_interval_data[1] - 1)->ccval;
Here it can also crash.

Getting a sender-based implementation right is complex, since it requires to
enforce consistency and garbage collection for so many data structures.

That is why I think it would be easier to start with a receiver-based implementation
and then grow it into a sender-based implementation if it shows promise.