[RFC2][PATCH 7/7] [TFRC]: New rx history code
Gerrit, I think I got this right this time, please see if there is anything left so that we can move on. I plan to go thru the following patches restricting myself to namespacing and consistency issues, leaving ideas I have for later, when we get more of your backlog merged. The first six patches in this series are unmodified, so if you are OK with them please send me your Signed-off-by. Thanks a lot, - Arnaldo From 2a3b4067dd514ce0e307d165783bc561cc7f17c4 Mon Sep 17 00:00:00 2001 From: Arnaldo Carvalho de Melo [EMAIL PROTECTED] Date: Thu, 6 Dec 2007 10:56:58 -0200 Subject: [PATCH 7/7] [TFRC]: New rx history code Credit here goes to Gerrit Renker, that provided the initial implementation for this new codebase. I modified it just to try to make it closer to the existing API, renaming some functions, add namespacing and fix one bug where the tfrc_rx_hist_alloc was not freeing the allocated ring entries on the error path. Original changeset comment from Gerrit: --- This provides a new, self-contained and generic RX history service for TFRC based protocols. Details: * new data structure, initialisation and cleanup routines; * allocation of dccp_rx_hist entries local to packet_history.c, as a service exported by the dccp_tfrc_lib module. * interface to automatically track highest-received seqno; * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1); * a generic function to test for `data packets' as per RFC 4340, sec. 7.7. Signed-off-by: Arnaldo Carvalho de Melo [EMAIL PROTECTED] --- net/dccp/ccids/ccid3.c | 292 +-- net/dccp/ccids/ccid3.h | 14 +- net/dccp/ccids/lib/loss_interval.c | 13 ++- net/dccp/ccids/lib/packet_history.c | 290 +-- net/dccp/ccids/lib/packet_history.h | 83 +-- 5 files changed, 334 insertions(+), 358 deletions(-) diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 5ff5aab..28a5e4d 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -641,6 +641,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, /* * Receiver Half-Connection Routines */ + +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE +}; + #ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { @@ -667,59 +676,60 @@ static void ccid3_hc_rx_set_state(struct sock *sk, hcrx-ccid3hcrx_state = state; } -static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len) -{ - if (likely(len 0))/* don't update on empty packets (e.g. ACKs) */ - hcrx-ccid3hcrx_s = tfrc_ewma(hcrx-ccid3hcrx_s, len, 9); -} - -static void ccid3_hc_rx_send_feedback(struct sock *sk) +static void ccid3_hc_rx_send_feedback(struct sock *sk, + const struct sk_buff *skb, + enum ccid3_fback_type fbtype) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct tfrc_rx_hist_entry *packet; ktime_t now; - suseconds_t delta; + s64 delta = 0; ccid3_pr_debug(%s(%p) - entry \n, dccp_role(sk), sk); + if (unlikely(hcrx-ccid3hcrx_state == TFRC_RSTATE_TERM)) + return; + now = ktime_get_real(); - switch (hcrx-ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: + switch (fbtype) { + case CCID3_FBACK_INITIAL: hcrx-ccid3hcrx_x_recv = 0; + hcrx-ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: - delta = ktime_us_delta(now, - hcrx-ccid3hcrx_tstamp_last_feedback); - DCCP_BUG_ON(delta 0); - hcrx-ccid3hcrx_x_recv = - scaled_div32(hcrx-ccid3hcrx_bytes_recv, delta); + case CCID3_FBACK_PARAM_CHANGE: + /* +* When parameters change (new loss or p p_prev), we do not +* have a reliable estimate for R_m of [RFC 3448, 6.2] and so +* need to reuse the previous value of X_recv. However, when +* X_recv was 0 (due to early loss), this would kill X down to +* s/t_mbi (i.e. one packet in 64 seconds). +* To avoid such drastic reduction, we approximate X_recv as +* the number of bytes since last feedback. +* This is a safe fallback, since X is bounded above by X_calc. +*/ + if (hcrx-ccid3hcrx_x_recv 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hcrx
Re: [RFC2][PATCH 7/7] [TFRC]: New rx history code
| The first six patches in this series are unmodified, so if you | are OK with them please send me your Signed-off-by. Patches [1/7], [2/7], and [6/7] already have a signed-off and there are no changes. Just acknowledged [3..5/7], will look at [7/7] now. Cheers Gerrit -- To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC2][PATCH 7/7] [TFRC]: New rx history code
Em Thu, Dec 06, 2007 at 02:02:25PM +, Gerrit Renker escreveu: | The first six patches in this series are unmodified, so if you | are OK with them please send me your Signed-off-by. Patches [1/7], [2/7], and [6/7] already have a signed-off and there are no changes. Just acknowledged [3..5/7], will look at [7/7] now. OK, please let me know if there are still any problems. The removal of timestamp insertion in ccid3_hc_rx_insert_options will be put in another cset. - Arnaldo -- To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 7/7] [TFRC]: New rx history code
Credit here goes to Gerrit Renker, that provided the initial implementation for this new codebase. I modified it just to try to make it closer to the existing API, renaming some functions, add namespacing and fix one bug where the tfrc_rx_hist_alloc was not freeing the allocated ring entries on the error path. Original changeset comment from Gerrit: --- This provides a new, self-contained and generic RX history service for TFRC based protocols. Details: * new data structure, initialisation and cleanup routines; * allocation of dccp_rx_hist entries local to packet_history.c, as a service exported by the dccp_tfrc_lib module. * interface to automatically track highest-received seqno; * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1); * a generic function to test for `data packets' as per RFC 4340, sec. 7.7. Signed-off-by: Gerrit Renker [EMAIL PROTECTED] Signed-off-by: Arnaldo Carvalho de Melo [EMAIL PROTECTED] --- net/dccp/ccids/ccid3.c | 288 -- net/dccp/ccids/ccid3.h | 14 +- net/dccp/ccids/lib/loss_interval.c | 13 ++- net/dccp/ccids/lib/packet_history.c | 290 +-- net/dccp/ccids/lib/packet_history.h | 83 +-- 5 files changed, 330 insertions(+), 358 deletions(-) diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 5ff5aab..faacffa 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -641,6 +641,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, /* * Receiver Half-Connection Routines */ + +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE +}; + #ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { @@ -667,59 +676,60 @@ static void ccid3_hc_rx_set_state(struct sock *sk, hcrx-ccid3hcrx_state = state; } -static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len) -{ - if (likely(len 0))/* don't update on empty packets (e.g. ACKs) */ - hcrx-ccid3hcrx_s = tfrc_ewma(hcrx-ccid3hcrx_s, len, 9); -} - -static void ccid3_hc_rx_send_feedback(struct sock *sk) +static void ccid3_hc_rx_send_feedback(struct sock *sk, + const struct sk_buff *skb, + enum ccid3_fback_type fbtype) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct tfrc_rx_hist_entry *packet; ktime_t now; - suseconds_t delta; + s64 delta = 0; ccid3_pr_debug(%s(%p) - entry \n, dccp_role(sk), sk); + if (unlikely(hcrx-ccid3hcrx_state == TFRC_RSTATE_TERM)) + return; + now = ktime_get_real(); - switch (hcrx-ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: + switch (fbtype) { + case CCID3_FBACK_INITIAL: hcrx-ccid3hcrx_x_recv = 0; + hcrx-ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: - delta = ktime_us_delta(now, - hcrx-ccid3hcrx_tstamp_last_feedback); - DCCP_BUG_ON(delta 0); - hcrx-ccid3hcrx_x_recv = - scaled_div32(hcrx-ccid3hcrx_bytes_recv, delta); + case CCID3_FBACK_PARAM_CHANGE: + /* +* When parameters change (new loss or p p_prev), we do not +* have a reliable estimate for R_m of [RFC 3448, 6.2] and so +* need to reuse the previous value of X_recv. However, when +* X_recv was 0 (due to early loss), this would kill X down to +* s/t_mbi (i.e. one packet in 64 seconds). +* To avoid such drastic reduction, we approximate X_recv as +* the number of bytes since last feedback. +* This is a safe fallback, since X is bounded above by X_calc. +*/ + if (hcrx-ccid3hcrx_x_recv 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hcrx-ccid3hcrx_tstamp_last_feedback); + if (delta = 0) + DCCP_BUG(delta (%ld) = 0, (long)delta); + else + hcrx-ccid3hcrx_x_recv = + scaled_div32(hcrx-ccid3hcrx_bytes_recv, delta); break; - case TFRC_RSTATE_TERM: - DCCP_BUG(%s(%p) - Illegal state TERM, dccp_role(sk), sk); + default: return; } - packet = tfrc_rx_hist_find_data_packet(hcrx-ccid3hcrx_hist); - if (unlikely(packet == NULL)) { - DCCP_WARN(%s(%p), no data
Re: [PATCH 7/7] [TFRC] New rx history code
| In the end this went back to the same questions and issues that were tackled between | February and March this year. I wish we could have had this dicussion then; it would | have made this email unnecessary. | | That is why it is important that the changeset comment collects these | scattered notes and discussions. Think about in some years from now we | will be left with a situation where we would have to look at many places | to understando some aspects of what is in the code. While this happens | and we have google for that I think that since you keep such detailed | notes it is not a problem to get them in the changesets. | I agree, the changelogs are all a bit short. When condensing from 40 to 16 patches the changelogs were also cut down, for fear of being too verbose. Will go through the patches in the next days and see if/where this can be improved, that would probably have saved some trouble. | * But where I need to interact is when changes are made to the algorithm, even if these may | seem small. The underlying reasons that lead to the code may not be immediately clear, | but since this is a solution for a specific problem, there are also specific reasons; which | is why for algorithm changes (and underlying data structure) I'd ask you to discuss this first | before committing the patch. | | I did this for the RX handling, where changes were made. Did that for | the TX but ended up commiting before comments from you, but I think its | fair to say that the changes for the TX history were more organizational | than in the essence of the algorithm. | It was a similar situation: the RFC patch came out on Thursday afternoon; I replied a bit hurriedly on Friday that it seemed ok, but found the full confirmation only on Sunday after putting all recent changes into the test tree. And yes, you made a good job of it. -- To unsubscribe from this list: send the line unsubscribe netdev in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 7/7] [TFRC] New rx history code
Em Wed, Dec 05, 2007 at 09:35:30AM +, Gerrit Renker escreveu: Quoting Arnaldo: | Em Tue, Dec 04, 2007 at 06:55:17AM +, Gerrit Renker escreveu: | NAK. You have changed the control flow of the algorithm and the underlying | data structure. Originally it had been an array of pointers, and this had | been a design decision right from the first submissions in March. From I | of http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt | | 1. 'ring' is an array of pointers rather than a contiguous area in | memory. The reason is that, when having to swap adjacent entries | to sort the history, it is easier to swap pointers than to copy | (heavy-weight) history-entry data structs. | | But in your algorithm it becomes a normal linear array. | | As a consequence all subsequent code needs to be rewritten to use | copying instead of swapping pointers. And there is a lot of that, since | the loss detection code makes heavy use of swapping entries in order to | cope with reordered and/or delayed packets. | | So lets not do that, the decision was made based on the RX history patch | alone, where, as pointed out, no swapping occurs. | | This is not what I would call entirely equivalent as you claim. Your | algorithm is fundamentally different, the control flow is not the same, | nor are the underlying data structures. | | Its is equivalent up to what is in the tree, thank you for point out | that in subsequent patches it will be used. | | Had this design decision been made explicit in the changeset comment | that introduces the data structure I wouldn't have tried to reduce the | number of allocations. | | And you even said that it was a good decision when first reacting to | this change, which I saw as positive feedback for the RFC I sent. | That was my fault. Your solution looked much better to me but even I had forgotten that the algorithm is based on an array of pointers. When I finally sat down And you wrote that code, I acted on looking the code together with reading the changeset comment, to me it also looked much better to do that, but as there were many changes, I sent an [RFC] message. It served its purpose, as you after two iterations realised it was in fact not a good idea as later an array of pointers is required. I should have taken that swap routine as the definitive hint that indeed it was needed. and looked through the patch set I found the original notes from March and saw that using a linear array instead of an array of pointers will require quite a few changes and means changing the algorithm. I then thought through whether there could be any advantage in using a linear array as in this patch, but could find none. In the end this went back to the same questions and issues that were tackled between February and March this year. I wish we could have had this dicussion then; it would have made this email unnecessary. That is why it is important that the changeset comment collects these scattered notes and discussions. Think about in some years from now we will be left with a situation where we would have to look at many places to understando some aspects of what is in the code. While this happens and we have google for that I think that since you keep such detailed notes it is not a problem to get them in the changesets. I thank you for your replay and I am sorry if you took offense at my perhaps a little strong reaction, here is the essence what I tried to convey but what maybe did not succeed in conveying: * I am absolutely ok with you making changes to variable names, namespaces, file organisation, overall arrangement etc (as per previous email). You have experience and this will often be a benefit. For instance, you combined tfrc_entry_from_skb() with tfrc_rx_hist_update() to give a new function, tfrc_rx_hist_add_packet(). This is ok since entry_from_skb() is not otherwise used (and I only found this out when reading your patch). (On the other hand, since this is a 4-element ring buffer, it is no real adding, the same entry will frequently be overwritten, this is why it was initially called hist_update().) From the RX history API user perspective (CCID3 right now, others may come) it is adding a packet to the history. In the past it went to a list, now we have a ring and don't keep more than TFRC_NDUPACK + 1 entries, but this is an internal detail that users don't need to know. * I am also not so much concerned about credit. As long as the (changed) end result is as least as good as or hopefully better than the submitted input, the author name is a side issue; so I do think that your approach is sound and fair. The only place where credits are needed is for the SatSix project (www.ist-satsix.org) which funded this work. This is why some of the
Re: [PATCH 7/7] [TFRC] New rx history code
Quoting Arnaldo: | Em Tue, Dec 04, 2007 at 06:55:17AM +, Gerrit Renker escreveu: | NAK. You have changed the control flow of the algorithm and the underlying | data structure. Originally it had been an array of pointers, and this had | been a design decision right from the first submissions in March. From I | of http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt | | 1. 'ring' is an array of pointers rather than a contiguous area in | memory. The reason is that, when having to swap adjacent entries | to sort the history, it is easier to swap pointers than to copy | (heavy-weight) history-entry data structs. | | But in your algorithm it becomes a normal linear array. | | As a consequence all subsequent code needs to be rewritten to use | copying instead of swapping pointers. And there is a lot of that, since | the loss detection code makes heavy use of swapping entries in order to | cope with reordered and/or delayed packets. | | So lets not do that, the decision was made based on the RX history patch | alone, where, as pointed out, no swapping occurs. | | This is not what I would call entirely equivalent as you claim. Your | algorithm is fundamentally different, the control flow is not the same, | nor are the underlying data structures. | | Its is equivalent up to what is in the tree, thank you for point out | that in subsequent patches it will be used. | | Had this design decision been made explicit in the changeset comment | that introduces the data structure I wouldn't have tried to reduce the | number of allocations. | | And you even said that it was a good decision when first reacting to | this change, which I saw as positive feedback for the RFC I sent. | That was my fault. Your solution looked much better to me but even I had forgotten that the algorithm is based on an array of pointers. When I finally sat down and looked through the patch set I found the original notes from March and saw that using a linear array instead of an array of pointers will require quite a few changes and means changing the algorithm. I then thought through whether there could be any advantage in using a linear array as in this patch, but could find none. In the end this went back to the same questions and issues that were tackled between February and March this year. I wish we could have had this dicussion then; it would have made this email unnecessary. I thank you for your replay and I am sorry if you took offense at my perhaps a little strong reaction, here is the essence what I tried to convey but what maybe did not succeed in conveying: * I am absolutely ok with you making changes to variable names, namespaces, file organisation, overall arrangement etc (as per previous email). You have experience and this will often be a benefit. For instance, you combined tfrc_entry_from_skb() with tfrc_rx_hist_update() to give a new function, tfrc_rx_hist_add_packet(). This is ok since entry_from_skb() is not otherwise used (and I only found this out when reading your patch). (On the other hand, since this is a 4-element ring buffer, it is no real adding, the same entry will frequently be overwritten, this is why it was initially called hist_update().) * I am also not so much concerned about credit. As long as the (changed) end result is as least as good as or hopefully better than the submitted input, the author name is a side issue; so I do think that your approach is sound and fair. The only place where credits are needed is for the SatSix project (www.ist-satsix.org) which funded this work. This is why some of the copyrights now included University of Aberdeen. What in any case I'd like to add is at least the Signed-off-by: if it turns out to be a mess I want to contribute my part of responsibility. * But where I need to interact is when changes are made to the algorithm, even if these may seem small. The underlying reasons that lead to the code may not be immediately clear, but since this is a solution for a specific problem, there are also specific reasons; which is why for algorithm changes (and underlying data structure) I'd ask you to discuss this first before committing the patch. * In part you are already doing this (message subject); it may be necessary to adapt the way of discussion/presentation. The subject is complex (spent a week with the flow chart only) and it is a lot - initially this had been 40 small patches. | | I modified it just to try to make it closer to the existing API, hide details from | | the CCIDs and fix a couple bugs found in the initial implementation. | What is a couple bugs? So far you have pointed out only one problem and that was | agreed, it can be fixed. But it remains a side issue, it is not a failure of the | | I pointed two problems one ended up being just the
Re: [PATCH 7/7] [TFRC] New rx history code
Em Tue, Dec 04, 2007 at 06:55:17AM +, Gerrit Renker escreveu: NAK. You have changed the control flow of the algorithm and the underlying data structure. Originally it had been an array of pointers, and this had been a design decision right from the first submissions in March. From I of http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt 1. 'ring' is an array of pointers rather than a contiguous area in memory. The reason is that, when having to swap adjacent entries to sort the history, it is easier to swap pointers than to copy (heavy-weight) history-entry data structs. But in your algorithm it becomes a normal linear array. As a consequence all subsequent code needs to be rewritten to use copying instead of swapping pointers. And there is a lot of that, since the loss detection code makes heavy use of swapping entries in order to cope with reordered and/or delayed packets. So lets not do that, the decision was made based on the RX history patch alone, where, as pointed out, no swapping occurs. This is not what I would call entirely equivalent as you claim. Your algorithm is fundamentally different, the control flow is not the same, nor are the underlying data structures. Its is equivalent up to what is in the tree, thank you for point out that in subsequent patches it will be used. Had this design decision been made explicit in the changeset comment that introduces the data structure I wouldn't have tried to reduce the number of allocations. And you even said that it was a good decision when first reacting to this change, which I saw as positive feedback for the RFC I sent. | Credit here goes to Gerrit Renker, that provided the initial implementation for | this new codebase. | | I modified it just to try to make it closer to the existing API, hide details from | the CCIDs and fix a couple bugs found in the initial implementation. What is a couple bugs? So far you have pointed out only one problem and that was agreed, it can be fixed. But it remains a side issue, it is not a failure of the I pointed two problems one ended up being just the fact that tfrc_ewma checks if the average is zero for every calculation. algorithm per se. What is worse here is that you take this single occurrence as a kind of carte blanche to mess around with the code as you please. Where please are the other bugs you are referring to? I mentioned in the previous messages, one was a problem, the other you clarified that was not a problem, but could be optimized. I am not buying into this and am not convinced that you are understanding what you are doing. It is the third time that you take patches which have been submitted on [EMAIL PROTECTED] for over half a year, for which you have offered no more than a sentence of feedback, release them under your name, and introduce fundamental changes which alter the behaviour. I commited it under my name because I changed it, while giving you credit. The first instance was the set of ktime patches which I had developed for the test tree and which you extended to DCCP. In this case it were in fact three bugs that you added in migrating my patches. I know this because it messed up the way CCID3 behaved and since I spent several hours chasing these. And, in contrast to the above, it is not a mere claim: that is recorded in the netdev mail archives. I'm sorry you feel so strongly when back and forth you express gratitude and then you show contempt for my behaviour. The second instance was when you released the TX history patches under your name. Pro forma there was an RFC patch at 3pm, de facto it was checked in a few hours later: input not welcome. Have you found any problems in it? Look again at the changeset to see if I stole your code as you seem to imply: commit 02271b56fd4028820e68e85e9d468628f42fb6ab Author: Arnaldo Carvalho de Melo [EMAIL PROTECTED] Date: Wed Nov 28 11:15:40 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
Re: [PATCH 7/7] [TFRC] New rx history code
NAK. You have changed the control flow of the algorithm and the underlying data structure. Originally it had been an array of pointers, and this had been a design decision right from the first submissions in March. From I of http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt 1. 'ring' is an array of pointers rather than a contiguous area in memory. The reason is that, when having to swap adjacent entries to sort the history, it is easier to swap pointers than to copy (heavy-weight) history-entry data structs. But in your algorithm it becomes a normal linear array. As a consequence all subsequent code needs to be rewritten to use copying instead of swapping pointers. And there is a lot of that, since the loss detection code makes heavy use of swapping entries in order to cope with reordered and/or delayed packets. This is not what I would call entirely equivalent as you claim. Your algorithm is fundamentally different, the control flow is not the same, nor are the underlying data structures. | Credit here goes to Gerrit Renker, that provided the initial implementation for | this new codebase. | | I modified it just to try to make it closer to the existing API, hide details from | the CCIDs and fix a couple bugs found in the initial implementation. What is a couple bugs? So far you have pointed out only one problem and that was agreed, it can be fixed. But it remains a side issue, it is not a failure of the algorithm per se. What is worse here is that you take this single occurrence as a kind of carte blanche to mess around with the code as you please. Where please are the other bugs you are referring to? I am not buying into this and am not convinced that you are understanding what you are doing. It is the third time that you take patches which have been submitted on [EMAIL PROTECTED] for over half a year, for which you have offered no more than a sentence of feedback, release them under your name, and introduce fundamental changes which alter the behaviour. The first instance was the set of ktime patches which I had developed for the test tree and which you extended to DCCP. In this case it were in fact three bugs that you added in migrating my patches. I know this because it messed up the way CCID3 behaved and since I spent several hours chasing these. And, in contrast to the above, it is not a mere claim: that is recorded in the netdev mail archives. The second instance was when you released the TX history patches under your name. Pro forma there was an RFC patch at 3pm, de facto it was checked in a few hours later: input not welcome. The third instance is now where you change in essence the floor underneath this work. Since you are using a different basis, the algorithm is (in addition to the changes in control flow) necessarily different. I have provided documentation, written test modules, and am able to prove that the algorithm as submitted works reasonably correct. In addition, the behaviour has been verified using regression tests. I am not prepared to take your claims and expressions of deepest respect at face value since your actions - not your words - show that you are, in fact, not dealing respectfully with work which has taken months to complete and verify. During 9 months on [EMAIL PROTECTED] you did not provide so much as a paragraph of feedback. Instead you mopped up code from the test tree, modified it according to your own whims and now, in the circle of your invitation-only buddies, start to talk about having discussions and iterations. The only iteration I can see is in fixing up the things you introduced, so it is not you who has to pay the price. Sorry, unless you can offer a more mature model of collaboration, consider me out of this and the patches summarily withdrawn. I am not prepared to throw away several months of work just because you feel inspired to do as you please with the work of others. Gerrit | Original changeset comment from Gerrit: | --- | This provides a new, self-contained and generic RX history service for TFRC | based protocols. | | Details: | * new data structure, initialisation and cleanup routines; | * allocation of dccp_rx_hist entries local to packet_history.c, |as a service exported by the dccp_tfrc_lib module. | * interface to automatically track highest-received seqno; | * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1); | * a generic function to test for `data packets' as per RFC 4340, sec. 7.7. | --- | | Signed-off-by: Arnaldo Carvalho de Melo [EMAIL PROTECTED] | --- | net/dccp/ccids/ccid3.c | 255 | net/dccp/ccids/ccid3.h | 14 +- | net/dccp/ccids/lib/loss_interval.c | 14 +- | net/dccp/ccids/lib/packet_history.c | 277 +++--- | net/dccp/ccids/lib/packet_history.h
[PATCH 7/7] [TFRC] New rx history code
Credit here goes to Gerrit Renker, that provided the initial implementation for this new codebase. I modified it just to try to make it closer to the existing API, hide details from the CCIDs and fix a couple bugs found in the initial implementation. Original changeset comment from Gerrit: --- This provides a new, self-contained and generic RX history service for TFRC based protocols. Details: * new data structure, initialisation and cleanup routines; * allocation of dccp_rx_hist entries local to packet_history.c, as a service exported by the dccp_tfrc_lib module. * interface to automatically track highest-received seqno; * receiver-based RTT estimation (needed for instance by RFC 3448, 6.3.1); * a generic function to test for `data packets' as per RFC 4340, sec. 7.7. --- Signed-off-by: Arnaldo Carvalho de Melo [EMAIL PROTECTED] --- net/dccp/ccids/ccid3.c | 255 net/dccp/ccids/ccid3.h | 14 +- net/dccp/ccids/lib/loss_interval.c | 14 +- net/dccp/ccids/lib/packet_history.c | 277 +++--- net/dccp/ccids/lib/packet_history.h | 82 +++- net/dccp/ccids/lib/packet_history_internal.h | 67 ++ 6 files changed, 353 insertions(+), 356 deletions(-) create mode 100644 net/dccp/ccids/lib/packet_history_internal.h diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 5ff5aab..af64c1d 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -641,6 +641,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, /* * Receiver Half-Connection Routines */ + +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE +}; + #ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { @@ -673,53 +682,60 @@ static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len) hcrx-ccid3hcrx_s = tfrc_ewma(hcrx-ccid3hcrx_s, len, 9); } -static void ccid3_hc_rx_send_feedback(struct sock *sk) +static void ccid3_hc_rx_send_feedback(struct sock *sk, + const struct sk_buff *skb, + enum ccid3_fback_type fbtype) { struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct tfrc_rx_hist_entry *packet; ktime_t now; - suseconds_t delta; + s64 delta = 0; ccid3_pr_debug(%s(%p) - entry \n, dccp_role(sk), sk); + if (unlikely(hcrx-ccid3hcrx_state == TFRC_RSTATE_TERM)) + return; + now = ktime_get_real(); - switch (hcrx-ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: + switch (fbtype) { + case CCID3_FBACK_INITIAL: hcrx-ccid3hcrx_x_recv = 0; + hcrx-ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: - delta = ktime_us_delta(now, - hcrx-ccid3hcrx_tstamp_last_feedback); - DCCP_BUG_ON(delta 0); - hcrx-ccid3hcrx_x_recv = - scaled_div32(hcrx-ccid3hcrx_bytes_recv, delta); + case CCID3_FBACK_PARAM_CHANGE: + /* +* When parameters change (new loss or p p_prev), we do not +* have a reliable estimate for R_m of [RFC 3448, 6.2] and so +* need to reuse the previous value of X_recv. However, when +* X_recv was 0 (due to early loss), this would kill X down to +* s/t_mbi (i.e. one packet in 64 seconds). +* To avoid such drastic reduction, we approximate X_recv as +* the number of bytes since last feedback. +* This is a safe fallback, since X is bounded above by X_calc. +*/ + if (hcrx-ccid3hcrx_x_recv 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hcrx-ccid3hcrx_tstamp_last_feedback); + if (delta = 0) + DCCP_BUG(delta (%ld) = 0, (long)delta); + else + hcrx-ccid3hcrx_x_recv = + scaled_div32(hcrx-ccid3hcrx_bytes_recv, delta); break; - case TFRC_RSTATE_TERM: - DCCP_BUG(%s(%p) - Illegal state TERM, dccp_role(sk), sk); + default: return; } - packet = tfrc_rx_hist_find_data_packet(hcrx-ccid3hcrx_hist); - if (unlikely(packet == NULL)) { - DCCP_WARN(%s(%p), no data packet in history!\n, - dccp_role(sk), sk); - return; - } +