Skip to contentSkip to conversation

Adds implementation of TFRC-SP sender side into the DCCP test tree

PATCH In review Ivo Calado 2 participants 9 messages Oct 13, 2009 – Nov 6, 2009 2 messages not in the archive

Subsystems (2)
lore
Share & tools
lore

Ivo Calado

author
#0 lore raw

cover Adds implementation of TFRC-SP sender side into the DCCP test tree

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.

author
#1 lore raw

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

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

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)

#2 lore raw

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

| 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);

A message that is not in the archive (sent off-list or not yet received): [email protected]

author
#4 lore raw

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

Quoted 20 lines · 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.

Quoted 8 lines

   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.

Quoted 10 lines

 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.

Quoted 7 lines

 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?

Quoted 9 lines

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.

Quoted 14 lines

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);
Quoted 9 lines

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.

Quoted 4 lines

(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?

Quoted 7 lines

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.

Signature · 9 lines
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.
#5 lore raw

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

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

A message that is not in the archive (sent off-list or not yet received): [email protected]

author
#7 lore raw

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

Quoted 5 lines · 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.
Quoted 7 lines

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.

Quoted 25 lines
| >  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.

Quoted 7 lines

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.

Quoted 12 lines
| > 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.

Quoted 9 lines

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.

Quoted 9 lines
| > (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?
Quoted 6 lines

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.

Signature · 12 lines
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.
author
#8 lore raw

PATCH 3/4 Implement dropped packets option

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

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_ */

#9 lore raw

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

| +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.

author
#10 lore raw

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

In reply to Ivo Calado
Quoted 43 lines · 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;
Quoted 3 lines

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

Thanks for observing this.

Quoted 9 lines

<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.

Thanks, will be fixed.

Quoted 4 lines

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

Yes, it can take time.

Quoted 2 lines

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.

Agreed.

Signature · 9 lines
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.