summaryrefslogtreecommitdiffstats
path: root/net/dccp/ccids
Commit message (Collapse)AuthorAgeFilesLines
* module_param: make bool parameters really bool (net & drivers/net)Rusty Russell2011-12-194-5/+5
| | | | | | | | | | | | | | | | module_param(bool) used to counter-intuitively take an int. In fddd5201 (mid-2009) we allowed bool or int/unsigned int using a messy trick. It's time to remove the int/unsigned int option. For this version it'll simply give a warning, but it'll break next kernel version. (Thanks to Joe Perches for suggesting coccinelle for 0/1 -> true/false). Cc: "David S. Miller" <davem@davemloft.net> Cc: netdev@vger.kernel.org Signed-off-by: Rusty Russell <rusty@rustcorp.com.au> Signed-off-by: David S. Miller <davem@davemloft.net>
* net: add moduleparam.h for users of module_param/MODULE_PARM_DESCPaul Gortmaker2011-10-311-0/+1
| | | | | | | | These files were getting access to these two via the implicit presence of module.h everywhere. They aren't modules, so they don't need the full module.h inclusion though. Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com>
* dccp ccid-2: check Ack Ratio when reducing cwndSamuel Jero2011-08-011-3/+23
| | | | | | | | | | | | | This patch causes CCID-2 to check the Ack Ratio after reducing the congestion window. If the Ack Ratio is greater than the congestion window, it is reduced. This prevents timeouts caused by an Ack Ratio larger than the congestion window. In this situation, we choose to set the Ack Ratio to half the congestion window (or one if that's zero) so that if we loose one ack we don't trigger a timeout. Signed-off-by: Samuel Jero <sj323707@ohio.edu> Acked-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: increment cwnd correctlySamuel Jero2011-08-011-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes an issue where CCID-2 will not increase the congestion window for numerous RTTs after an idle period, application-limited period, or a loss once the algorithm is in Congestion Avoidance. What happens is that, when CCID-2 is in Congestion Avoidance mode, it will increase hc->tx_packets_acked by one for every packet and will increment cwnd every cwnd packets. However, if there is now an idle period in the connection, cwnd will be reduced, possibly below the slow start threshold. This will cause the connection to go into Slow Start. However, in Slow Start CCID-2 performs this test to increment cwnd every second ack: ++hc->tx_packets_acked == 2 Unfortunately, this will be incorrect, if cwnd previous to the idle period was larger than 2 and if tx_packets_acked was close to cwnd. For example: cwnd=50 and tx_packets_acked=45. In this case, the current code, will increment tx_packets_acked until it equals two, which will only be once tx_packets_acked (an unsigned 32-bit integer) overflows. My fix is simply to change that test for tx_packets_acked greater than or equal to two in slow start. Signed-off-by: Samuel Jero <sj323707@ohio.edu> Acked-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: prevent cwnd > Sequence WindowSamuel Jero2011-08-012-15/+41
| | | | | | | | | | | | | | | | | | | | | | Add a check to prevent CCID-2 from increasing the cwnd greater than the Sequence Window. When the congestion window becomes bigger than the Sequence Window, CCID-2 will attempt to keep more data in the network than the DCCP Sequence Window code considers possible. This results in the Sequence Window code issuing a Sync, thereby inducing needless overhead. Further, if this occurs at the sender, CCID-2 will never detect the problem because the Acks it receives will indicate no losses. I have seen this cause a drop of 1/3rd in throughput for a connection. Also add code to adjust the Sequence Window to be about 5 times the number of packets in the network (RFC 4340, 7.5.2) and to adjust the Ack Ratio so that the remote Sequence Window will hold about 5 times the number of packets in the network. This allows the congestion window to increase correctly without being limited by the Sequence Window. Signed-off-by: Samuel Jero <sj323707@ohio.edu> Acked-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: use feature-negotiation to report Ack Ratio changesGerrit Renker2011-08-011-1/+9
| | | | | | | | | | | | | This uses the new feature-negotiation framework to signal Ack Ratio changes, as required by RFC 4341, sec. 6.1.2. That raises some problems with CCID-2, which at the moment can not cope gracefully with Ack Ratios > 1. Since these issues are not directly related to feature negotiation, they are marked by a FIXME. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: Samuel Jero <sj323707@ohio.edu> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.uk>
* dccp ccid-2: Perform congestion-window validationGerrit Renker2011-07-042-3/+91
| | | | | | | | | | | | | | | | | | | | | | | | | | | | CCID-2's cwnd increases like TCP during slow-start, which has implications for * the local Sequence Window value (should be > cwnd), * the Ack Ratio value. Hence an exponential growth, if it does not reflect the actual network conditions, can quickly lead to instability. This patch adds congestion-window validation (RFC2861) to CCID-2: * cwnd is constrained if the sender is application limited; * cwnd is reduced after a long idle period, as suggested in the '90 paper by Van Jacobson, in RFC 2581 (sec. 4.1); * cwnd is never reduced below the RFC 3390 initial window. As marked in the comments, the code is actually almost a direct copy of the TCP congestion-window-validation algorithms. By continuing this work, it may in future be possible to use the TCP code (not possible at the moment). The mechanism can be turned off using a module parameter. Sampling of the currently-used window (moving-maximum) is however done constantly; this is used to determine the expected window, which can be exploited to regulate DCCP's Sequence Window value. This patch also sets slow-start-after-idle (RFC 4341, 5.1), i.e. it behaves like TCP when net.ipv4.tcp_slow_start_after_idle = 1. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Use existing function to test for data packetsGerrit Renker2011-07-042-11/+11
| | | | | | | | | This replaces a switch statement with a test, using the equivalent function dccp_data_packet(skb). It also doubles the range of the field `rx_num_data_pkts' by changing the type from `int' to `u32', avoiding signed/unsigned comparison with the u16 field `dccps_r_ack_ratio'. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: move rfc 3390 function into header fileGerrit Renker2011-07-042-9/+9
| | | | | | | | This moves CCID-2's initial window function into the header file, since several parts throughout the CCID-2 code need to call it (CCID-2 still uses RFC 3390). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Leandro Melo de Sales <leandro@ic.ufal.br>
* tcp: Increase the initial congestion window to 10.David S. Miller2011-02-021-0/+9
| | | | | Signed-off-by: David S. Miller <davem@davemloft.net> Acked-by: Nandita Dukkipati <nanditad@google.com>
* dccp ccid-2: Separate option parsing from CCID processingGerrit Renker2010-11-152-93/+43
| | | | | | | | | | | | | | | | This patch replaces an almost identical replication of code: large parts of dccp_parse_options() re-appeared as ccid2_ackvector() in ccid2.c. Apart from the duplication, this caused two more problems: 1. CCIDs should not need to be concerned with parsing header options; 2. one can not assume that Ack Vectors appear as a contiguous area within an skb, it is legal to insert other options and/or padding in between. The current code would throw an error and stop reading in such a case. Since Ack Vectors provide CCID-specific information, they are now processed by the CCID directly, separating this functionality from the main DCCP code. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Ack Vector interface clean-upGerrit Renker2010-11-101-8/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch brings the Ack Vector interface up to date. Its main purpose is to lay the basis for the subsequent patches of this set, which will use the new data structure fields and routines. There are no real algorithmic changes, rather an adaptation: (1) Replaced the static Ack Vector size (2) with a #define so that it can be adapted (with low loss / Ack Ratio, a value of 1 works, so 2 seems to be sufficient for the moment) and added a solution so that computing the ECN nonce will continue to work - even with larger Ack Vectors. (2) Replaced the #defines for Ack Vector states with a complete enum. (3) Replaced #defines to compute Ack Vector length and state with general purpose routines (inlines), and updated code to use these. (4) Added a `tail' field (conversion to circular buffer in subsequent patch). (5) Updated the (outdated) documentation for Ack Vector struct. (6) All sequence number containers now trimmed to 48 bits. (7) Removal of unused bits: * removed dccpav_ack_nonce from struct dccp_ackvec, since this is already redundantly stored in the `dccpavr_ack_nonce' (of Ack Vector record); * removed Elapsed Time for Ack Vectors (it was nowhere used); * replaced semantics of dccpavr_sent_len with dccpavr_ack_runlen, since the code needs to be able to remember the old run length; * reduced the de-/allocation routines (redundant / duplicate tests). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Stop pollingGerrit Renker2010-10-282-8/+20
| | | | | | | | This updates CCID-2 to use the CCID dequeuing mechanism, converting from previous continuous-polling to a now event-driven mechanism. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: Return-value convention of hc_tx_send_packet()Gerrit Renker2010-10-281-6/+6
| | | | | | | | | | | | | | | | | | | This patch reorganises the return value convention of the CCID TX sending function, to permit more flexible schemes, as required by subsequent patches. Currently the convention is * values < 0 mean error, * a value == 0 means "send now", and * a value x > 0 means "send in x milliseconds". The patch provides symbolic constants and a function to interpret return values. In addition, it caps the maximum positive return value to 0xFFFF milliseconds, corresponding to 65.535 seconds. This is possible since in CCID-3/4 the maximum possible inter-packet gap is fixed at t_mbi = 64 sec. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: remove unused argument in CCID tx functionGerrit Renker2010-10-122-3/+2
| | | | | | | | | | | This removes the argument `more' from ccid_hc_tx_packet_sent, since it was nowhere used in the entire code. (Btw, this argument was not even used in the original KAME code where the function initially came from; compare the variable moreToSend in the freebsd61-dccp-kame-28.08.2006.patch kept by Emmanuel Lochin.) Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* net: return operator cleanupEric Dumazet2010-09-231-1/+1
| | | | | | | | | Change "return (EXPR);" to "return EXPR;" return is not a function, parentheses are not required. Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-3: Remove redundant 'options_received' structGerrit Renker2010-09-212-23/+8
| | | | | | | | The `options_received' struct is redundant, since it re-duplicates the existing `p' and `x_recv' fields. This patch removes the sub-struct and migrates the format conversion operations to ccid3_hc_tx_parse_options(). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc/ccid-3: computing the loss rate from the Loss Event RateGerrit Renker2010-09-213-5/+19
| | | | | | | | | | | | | | This adds a function to take care of the following, separate cases occurring in the computation of the Loss Rate p: * 1/(2^32-1) is mapped into 0% as per RFC 4342, 8.5; * 1/0 is mapped into 100%, the maximum; * to avoid that p = 1/x is rounded down to 0 when x is very large, since this means accidentally re-entering slow-start indicated by p == 0, the minimum resolution value of p is now returned instead; * a bug in ccid3_hc_rx_getsockopt is fixed: 1/0 was mapped into ~0U. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: remove dead statesGerrit Renker2010-09-212-30/+9
| | | | | | | | | | | | | | This patch is thanks to an investigation by Leandro Sales de Melo and his colleagues. They worked out two state diagrams which highlight the fact that the xxx_TERM states in CCID-3/4 are in fact not necessary. And this can be confirmed by in turn looking at the code: the xxx_TERM states are only ever set in ccid3_hc_{rx,tx}_exit(): when CCID-3 sets the state to xxx_TERM, it is at a time where no more processing should be going on, hence it is not necessary to introduce a dedicated exit state - this is already implied by unloading the CCID. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Add packet type information to CCID-specific option parsingGerrit Renker2010-09-211-6/+8
| | | | | | | | | | | | | | | | | This 1. adds packet type information to ccid_hc_{rx,tx}_parse_options(). This is necessary, since table 3 in RFC 4340, 5.8 leaves it to the CCIDs to state which options may (not) appear on what packet type. 2. adds such a check for CCID-3's {Loss Event, Receive} Rate as specified in RFC 4340 8.3 ("Receive Rate options MUST NOT be sent on DCCP-Data packets") and 8.5 ("Loss Event Rate options MUST NOT be sent on DCCP-Data packets"). 3. removes an unused argument `idx' from ccid_hc_{rx,tx}_parse_options(). This is also no longer necessary, since the CCID-specific option-parsing routines are passed every single parameter of the type-length-value option encoding. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Simplify and consolidate tx_parse_optionsGerrit Renker2010-09-152-46/+14
| | | | | | | | | | | | | | | | | | | | | | | | This simplifies and consolidates the TX option-parsing code: 1. The Loss Intervals option is not currently used, so dead code related to this option is removed. I am aware of no plans to support the option, but if someone wants to implement it (e.g. for inter-op tests), it is better to start afresh than having to also update currently unused code. 2. The Loss Event and Receive Rate options have a lot of code in common (both are 32 bit, both have same length etc.), so this is consolidated. 3. The test against GSR is not necessary, because - on first loading CCID3, ccid_new() zeroes out all fields in the socket; - ccid3_hc_tx_packet_recv() treats 0 and ~0U equivalently, due to pinv = opt_recv->ccid3or_loss_event_rate; if (pinv == ~0U || pinv == 0) hctx->p = 0; - as a result, the sequence number field is removed from opt_recv. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: remove buggy RTT-sampling history lookupGerrit Renker2010-09-153-57/+38
| | | | | | | | | | | | | | | | | | | | | | | This removes the RTT-sampling function tfrc_tx_hist_rtt(), since 1. it suffered from complex passing of return values (the return value both indicated successful lookup while the value doubled as RTT sample); 2. when for some odd reason the sample value equalled 0, this triggered a bug warning about "bogus Ack", due to the ambiguity of the return value; 3. on a passive host which has not sent anything the TX history is empty and thus will lead to unwanted "bogus Ack" warnings such as ccid3_hc_tx_packet_recv: server(e7b7d518): DATAACK with bogus ACK-28197148 ccid3_hc_tx_packet_recv: server(e7b7d518): DATAACK with bogus ACK-26641606. The fix is to replace the implicit encoding by performing the steps manually. Furthermore, the "bogus Ack" warning has been removed, since it can actually be triggered due to several reasons (network reordering, old packet, (3) above), hence it is not very useful. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: A lower bound for the inter-packet scheduling algorithmGerrit Renker2010-09-152-16/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fixes a subtle bug in the calculation of the inter-packet gap and shows that t_delta, as it is currently used, is not needed. The algorithm from RFC 5348, 8.3 below continually computes a send time t_nom, which is initialised with the current time t_now; t_gran = 1E6 / HZ specifies the scheduling granularity, s the packet size, and X the sending rate: t_distance = t_nom - t_now; // in microseconds t_delta = min(t_ipi, t_gran) / 2; // `delta' parameter in microseconds if (t_distance >= t_delta) { reschedule after (t_distance / 1000) milliseconds; } else { t_ipi = s / X; // inter-packet interval in usec t_nom += t_ipi; // compute the next send time send packet now; } Problem: -------- Rescheduling requires a conversion into milliseconds (sk_reset_timer()). The highest jiffy resolution with HZ=1000 is 1 millisecond, so using a higher granularity does not make much sense here. As a consequence, values of t_distance < 1000 are truncated to 0. This issue has so far been resolved by using instead if (t_distance >= t_delta + 1000) reschedule after (t_distance / 1000) milliseconds; This is unnecessarily large, a lower bound is t_delta' = max(t_delta, 1000). And it implies a further simplification: a) when HZ >= 500, then t_delta <= t_gran/2 = 10^6/(2*HZ) <= 1000, so that t_delta' = MAX(1000, t_delta) = 1000 (constant value); b) when HZ < 500, then t_delta = 1/2*MIN(rtt, t_ipi, t_gran) <= t_gran/2, so that 1000 <= t_delta' <= t_gran/2. The maximum error of using a constant t_delta in (b) is less than half a jiffy. Fix: ---- The patch replaces t_delta with a constant, whose value depends on CONFIG_HZ, changing the above algorithm to: if (t_distance >= t_delta') reschedule after (t_distance / 1000) milliseconds; where t_delta' = 10^6/(2*HZ) if HZ < 500, and t_delta' = 1000 otherwise. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: use per-route RTO or TCP RTO as fallbackGerrit Renker2010-08-303-38/+6
| | | | | | | | | | | | | | | | | | | | | | This makes RTAX_RTO_MIN also available to CCID-3, replacing the compile-time RTO lower bound with a per-route tunable value. The original Kconfig option solved the problem that a very low RTT (in the order of HZ) can trigger too frequent and unnecessary reductions of the sending rate. This tunable does not affect the initial RTO value of 2 seconds specified in RFC 5348, section 4.2 and Appendix B. But like the hardcoded Kconfig value, it allows to adapt to network conditions. The same effect as the original Kconfig option of 100ms is now achieved by > ip route replace to unicast 192.168.0.0/24 rto_min 100j dev eth0 (assuming HZ=1000). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Share TCP's minimum RTO codeGerrit Renker2010-08-301-2/+3
| | | | | | | | | | | | | | | | | | | | | | | | Using a fixed RTO_MIN of 0.2 seconds was found to cause problems for CCID-2 over 802.11g: at least once per session there was a spurious timeout. It helped to then increase the the value of RTO_MIN over this link. Since the problem is the same as in TCP, this patch makes the solution from commit "05bb1fad1cde025a864a90cfeb98dcbefe78a44a" "[TCP]: Allow minimum RTO to be configurable via routing metrics." available to DCCP. This avoids reinventing the wheel, so that e.g. the following works in the expected way now also for CCID-2: > ip route change 10.0.0.2 rto_min 800 dev ath0 Luckily this useful rto_min function was recently moved to net/tcp.h, which simplifies sharing code originating from TCP. Documentation also updated (plus minor whitespace fixes). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* tcp/dccp: Consolidate common code for RFC 3390 conversionGerrit Renker2010-08-301-6/+2
| | | | | | | | | This patch consolidates initial-window code common to TCP and CCID-2: * TCP uses RFC 3390 in a packet-oriented manner (tcp_input.c) and * CCID-2 uses RFC 3390 in packet-oriented manner (RFC 4341). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Remove wrappers around sk_{reset,stop}_timer()Gerrit Renker2010-08-301-25/+3
| | | | | | | | | | | | | | | | | This removes the wrappers around the sk timer functions, since not much is gained from using them: the BUG_ON in start_rto_timer will never trigger since that function is called only if: * the RTO timer expires (rto_expire, and then timer_pending() is false); * in tx_packet_sent only if !timer_pending() (BUG_ON is redundant here); * previously in new_ack, after stopping the timer (timer_pending() false). Removing the wrappers also clears the way for eventually replacing the RTO timer with the icsk-retransmission-timer, as it is already part of the DCCP socket. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Use u32 timestamps uniformlyGerrit Renker2010-08-302-13/+16
| | | | | | | | | | | | | | Since CCID-2 is de facto a mini implementation of TCP, it makes sense to share as much code as possible. Hence this patch aligns CCID-2 timestamping with TCP timestamping. This also halves the space consumption (on 64-bit systems). The necessary include file <net/tcp.h> is already included by way of net/dccp.h. Redundant includes have been removed. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Replace broken RTT estimator with better algorithmGerrit Renker2010-08-232-81/+108
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The current CCID-2 RTT estimator code is in parts broken and lags behind the suggestions in RFC2988 of using scaled variants for SRTT/RTTVAR. That code is replaced by the present patch, which reuses the Linux TCP RTT estimator code. Further details: ---------------- 1. The minimum RTO of previously one second has been replaced with TCP's, since RFC4341, sec. 5 says that the minimum of 1 sec. (suggested in RFC2988, 2.4) is not necessary. Instead, the TCP_RTO_MIN is used, which agrees with DCCP's concept of a default RTT (RFC 4340, 3.4). 2. The maximum RTO has been set to DCCP_RTO_MAX (64 sec), which agrees with RFC2988, (2.5). 3. De-inlined the function ccid2_new_ack(). 4. Added a FIXME: the RTT is sampled several times per Ack Vector, which will give the wrong estimate. It should be replaced with one sample per Ack. However, at the moment this can not be resolved easily, since - it depends on TX history code (which also needs some work), - the cleanest solution is not to use the `sent' time at all (saves 4 bytes per entry) and use DCCP timestamps / elapsed time to estimated the RTT, which however is non-trivial to get right (but needs to be done). Reasons for reusing the Linux TCP estimator algorithm: ------------------------------------------------------ Some time was spent to find a better alternative, using basic RFC2988 as a first step. Further analysis and experimentation showed that the Linux TCP RTO estimator is superior to a basic RFC2988 implementation. A summary is on http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid2/rto_estimator/ In addition, this estimator fared well in a recent empirical evaluation: Rewaskar, Sushant, Jasleen Kaur and F. Donelson Smith. A Performance Study of Loss Detection/Recovery in Real-world TCP Implementations. Proceedings of 15th IEEE International Conference on Network Protocols (ICNP-07), 2007. Thus there is significant benefit in reusing the existing TCP code. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Simplify dec_pipe and rearming of RTO timerGerrit Renker2010-08-231-19/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This removes the dec_pipe function and improves the way the RTO timer is rearmed when a new acknowledgment comes in. Details and justification for removal: -------------------------------------- 1) The BUG_ON in dec_pipe is never triggered: pipe is only decremented for TX history entries between tail and head, for which it had previously been incremented in tx_packet_sent; and it is not decremented twice for the same entry, since it is - either decremented when a corresponding Ack Vector cell in state 0 or 1 was received (and then ccid2s_acked==1), - or it is decremented when ccid2s_acked==0, as part of the loss detection in tx_packet_recv (and hence it can not have been decremented earlier). 2) Restarting the RTO timer happens for every single entry in each Ack Vector parsed by tx_packet_recv (according to RFC 4340, 11.4 this can happen up to 16192 times per Ack Vector). 3) The RTO timer should not be restarted when all outstanding data has been acknowledged. This is currently done similar to (2), in dec_pipe, when pipe has reached 0. The patch onsolidates the code which rearms the RTO timer, combining the segments from new_ack and dec_pipe. As a result, the code becomes clearer (compare with tcp_rearm_rto()). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Remove redundant sanity testsGerrit Renker2010-08-231-52/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This removes the ccid2_hc_tx_check_sanity function: it is redundant. Details: The tx_check_sanity function performs three tests: 1) it checks that the circular TX list is sorted - in ascending order of sequence number (ccid2s_seq) - and time (ccid2s_sent), - in the direction from `tail' (hctx_seqt) to `head' (hctx_seqh); 2) it ensures that the entire list has the length seqbufc * CCID2_SEQBUF_LEN; 3) it ensures that pipe equals the number of packets that were not marked `acked' (ccid2s_acked) between `tail' and `head'. The following argues that each of these tests is redundant, this can be verified by going through the code. (1) is not necessary, since both time and GSS increase from one packet to the next, so that subsequent insertions in tx_packet_sent (which advance the `head' pointer) will be in ascending order of time and sequence number. In (2), the length of the list is always equal to seqbufc times CCID2_SEQBUF_LEN (set to 1024) unless allocation caused an earlier failure, because: * at initialisation (tx_init), there is one chunk of size 1024 and seqbufc=1; * subsequent calls to tx_alloc_seq take place whenever head->next == tail in tx_packet_sent; then a new chunk of size 1024 is inserted between head and tail, and seqbufc is incremented by one. To show that (3) is redundant requires looking at two cases. The `pipe' variable of the TX socket is incremented only in tx_packet_sent, and decremented in tx_packet_recv. When head == tail (TX history empty) then pipe should be 0, which is the case directly after initialisation and after a retransmission timeout has occurred (ccid2_hc_tx_rto_expire). The first case involves parsing Ack Vectors for packets recorded in the live portion of the buffer, between tail and head. For each packet marked by the receiver as received (state 0) or ECN-marked (state 1), pipe is decremented by one, so for all such packets the BUG_ON in tx_check_sanity will not trigger. The second case is the loss detection in the second half of tx_packet_recv, below the comment "Check for NUMDUPACK". The first while-loop here ensures that the sequence number of `seqp' is either above or equal to `high_ack', or otherwise equal to the highest sequence number sent so far (of the entry head->prev, as head points to the next unsent entry). The next while-loop ("while (1)") counts the number of acked packets starting from that position of seqp, going backwards in the direction from head->prev to tail. If NUMDUPACK=3 such packets were counted within this loop, `seqp' points to the last acknowledged packet of these, and the "if (done == NUMDUPACK)" block is entered next. The while-loop contained within that block in turn traverses the list backwards, from head to tail; the position of `seqp' is saved in the variable `last_acked'. For each packet not marked as `acked', a congestion event is triggered within the loop, and pipe is decremented. The loop terminates when `seqp' has reached `tail', whereupon tail is set to the position previously stored in `last_acked'. Thus, between `last_acked' and the previous position of `tail', - pipe has been decremented earlier if the packet was marked as state 0 or 1; - pipe was decremented if the packet was not marked as acked. That is, pipe has been decremented by the number of packets between `last_acked' and the previous position of `tail'. As a consequence, pipe now again reflects the number of packets which have not (yet) been acked between the new position of tail (at `last_acked') and head->prev, or 0 if head==tail. The result is that the BUG_ON condition in check_sanity will also not be triggered, hence the test (3) is also redundant. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-3: No more CCID control blocks in LISTEN stateGerrit Renker2010-08-231-33/+7
| | | | | | | | | | | | | | | | | | | | | | | | The CCIDs are activated as last of the features, at the end of the handshake, were the LISTEN state of the master socket is inherited into the server state of the child socket. Thus, the only states visible to CCIDs now are OPEN/PARTOPEN, and the closing states. This allows to remove tests which were previously necessary to protect against referencing a socket in the listening state (in CCID-3), but which now have become redundant. As a further byproduct of enabling the CCIDs only after the connection has been fully established, several typecast-initialisations of ccid3_hc_{rx,tx}_sock can now be eliminated: * the CCID is loaded, so it is not necessary to test if it is NULL, * if it is possible to load a CCID and leave the private area NULL, then this is a bug, which should crash loudly - and earlier, * the test for state==OPEN || state==PARTOPEN now reduces only to the closing phase (e.g. when the node has received an unexpected Reset). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz> Signed-off-by: David S. Miller <davem@davemloft.net>
* ccid: ccid-2/3 code cosmeticsGerrit Renker2010-08-233-26/+27
| | | | | | | | | | | | | | | This patch collects cosmetics-only changes to separate these from code changes: * update with regard to CodingStyle and whitespace changes, * documentation: - adding/revising comments, - remove CCID-3 RX socket documentation which is either duplicate or refers to fields that no longer exist, * expand embedded tfrc_tx_info struct inline for consistency, removing indirections via #define. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: remove unused function argumentGerrit Renker2010-06-251-2/+2
| | | | | | | This removes an unused 'sk' argument from several option-inserting functions. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* Merge branch 'master' of ↵David S. Miller2010-04-111-0/+1
|\ | | | | | | | | | | | | | | | | | | | | | | master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6 Conflicts: drivers/net/stmmac/stmmac_main.c drivers/net/wireless/wl12xx/wl1271_cmd.c drivers/net/wireless/wl12xx/wl1271_main.c drivers/net/wireless/wl12xx/wl1271_spi.c net/core/ethtool.c net/mac80211/scan.c
| * include cleanup: Update gfp.h and slab.h includes to prepare for breaking ↵Tejun Heo2010-03-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | implicit slab.h inclusion from percpu.h percpu.h is included by sched.h and module.h and thus ends up being included when building most .c files. percpu.h includes slab.h which in turn includes gfp.h making everything defined by the two files universally available and complicating inclusion dependencies. percpu.h -> slab.h dependency is about to be removed. Prepare for this change by updating users of gfp and slab facilities include those headers directly instead of assuming availability. As this conversion needs to touch large number of source files, the following script is used as the basis of conversion. http://userweb.kernel.org/~tj/misc/slabh-sweep.py The script does the followings. * Scan files for gfp and slab usages and update includes such that only the necessary includes are there. ie. if only gfp is used, gfp.h, if slab is used, slab.h. * When the script inserts a new include, it looks at the include blocks and try to put the new include such that its order conforms to its surrounding. It's put in the include block which contains core kernel includes, in the same order that the rest are ordered - alphabetical, Christmas tree, rev-Xmas-tree or at the end if there doesn't seem to be any matching order. * If the script can't find a place to put a new include (mostly because the file doesn't have fitting include block), it prints out an error message indicating which .h file needs to be added to the file. The conversion was done in the following steps. 1. The initial automatic conversion of all .c files updated slightly over 4000 files, deleting around 700 includes and adding ~480 gfp.h and ~3000 slab.h inclusions. The script emitted errors for ~400 files. 2. Each error was manually checked. Some didn't need the inclusion, some needed manual addition while adding it to implementation .h or embedding .c file was more appropriate for others. This step added inclusions to around 150 files. 3. The script was run again and the output was compared to the edits from #2 to make sure no file was left behind. 4. Several build tests were done and a couple of problems were fixed. e.g. lib/decompress_*.c used malloc/free() wrappers around slab APIs requiring slab.h to be added manually. 5. The script was run on all .h files but without automatically editing them as sprinkling gfp.h and slab.h inclusions around .h files could easily lead to inclusion dependency hell. Most gfp.h inclusion directives were ignored as stuff from gfp.h was usually wildly available and often used in preprocessor macros. Each slab.h inclusion directive was examined and added manually as necessary. 6. percpu.h was updated not to include slab.h. 7. Build test were done on the following configurations and failures were fixed. CONFIG_GCOV_KERNEL was turned off for all tests (as my distributed build env didn't work with gcov compiles) and a few more options had to be turned off depending on archs to make things build (like ipr on powerpc/64 which failed due to missing writeq). * x86 and x86_64 UP and SMP allmodconfig and a custom test config. * powerpc and powerpc64 SMP allmodconfig * sparc and sparc64 SMP allmodconfig * ia64 SMP allmodconfig * s390 SMP allmodconfig * alpha SMP allmodconfig * um on x86_64 SMP allmodconfig 8. percpu.h modifications were reverted so that it could be applied as a separate patch and serve as bisection point. Given the fact that I had only a couple of failures from tests on step 6, I'm fairly confident about the coverage of this conversion patch. If there is a breakage, it's likely to be something in one of the arch headers which should be easily discoverable easily on most builds of the specific arch. Signed-off-by: Tejun Heo <tj@kernel.org> Guess-its-ok-by: Christoph Lameter <cl@linux-foundation.org> Cc: Ingo Molnar <mingo@redhat.com> Cc: Lee Schermerhorn <Lee.Schermerhorn@hp.com>
* | net: remove trailing space in messagesFrans Pop2010-03-241-1/+1
|/ | | | | Signed-off-by: Frans Pop <elendil@planet.nl> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-3: Remove CCID naming redundancy 2/2Gerrit Renker2009-10-071-186/+185
| | | | | | | | This continues the previous patch, by applying the same change to CCID-3. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Arnaldo Carvalho de Melo <acme@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Remove CCID naming redundancy 1/2Gerrit Renker2009-10-071-161/+161
| | | | | | | | | | | | | This removes a redundancy in the CCID half-connection (hc) naming scheme: * instead of 'hctx->tx_...', write 'hc->tx_...'; * instead of 'hcrx->rx_...', write 'hc->rx_...'; which works because the 'type' of the half-connection is encoded in the 'rx_' / 'tx_' prefixes. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Arnaldo Carvalho de Melo <acme@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-3: Overhaul CCID naming convention 2/2Gerrit Renker2009-10-072-232/+209
| | | | | | | | This implements the new naming scheme also for CCID-3. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Arnaldo Carvalho de Melo <acme@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-2: Overhaul CCID naming convention 1/2Gerrit Renker2009-10-072-161/+158
| | | | | | | | | | | | | | | | | | | | | | | This patch starts a less problematic naming convention for CCID structs. The old naming convention used 'hc{tx,rx}->ccid?hc{tx,rx}->...' as recurring prefixes, which made the code * hard to write (not easy to fit into 80 characters); * hard to read (most of the space is occupied by prefixes). The new naming scheme: * struct entries for the TX socket are prefixed by 'tx_'; * and those for the RX socket are prefixed by 'rx_'. The identifiers then remain distinguishable when grep-ing through the tree: (a) RX/TX sockets are distinguished by the naming scheme, (b) individual CCIDs are distinguished by filename (ccid{2,3,4}.{c,h}). This first patch implements the scheme for CCID-2. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Arnaldo Carvalho de Melo <acme@redhat.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* net-next-2.6 [PATCH 1/1] dccp: ccids whitespace-cleanup / CodingStyleGerrit Renker2009-09-1411-67/+48
| | | | | | | | | | | | | | | No code change, cosmetical changes only: * whitespace cleanup via scripts/cleanfile, * remove self-references to filename at top of files, * fix coding style (extraneous brackets), * fix documentation style (kernel-doc-nano-HOWTO). Thanks are due to Ivo Augusto Calado who raised these issues by submitting good-quality patches. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* net: mark read-only arrays as constJan Engelhardt2009-08-051-2/+2
| | | | | | | | String literals are constant, and usually, we can also tag the array of pointers const too, moving it to the .rodata section. Signed-off-by: Jan Engelhardt <jengelh@medozas.de> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp ccid-3: Fix RFC referenceGerrit Renker2009-01-111-1/+1
| | | | | | | | Thanks to Wei and Arnaldo for pointing out the correct new reference for CCID-3. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* net: fix section mismatch warnings in dccp/ccids/lib/tfrc.cLeonardo Potenza2009-01-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | Removed the __exit annotation of tfrc_lib_exit(), in order to suppress the following section mismatch messages: WARNING: net/dccp/dccp.o(.text+0xd9): Section mismatch in reference from the function ccid_cleanup_builtins() to the function .exit.text:tfrc_lib_exit() The function ccid_cleanup_builtins() references a function in an exit section. Often the function tfrc_lib_exit() has valid usage outside the exit section and the fix is to remove the __exit annotation of tfrc_lib_exit. WARNING: net/dccp/dccp.o(.init.text+0x48): Section mismatch in reference from the function ccid_initialize_builtins() to the function .exit.text:tfrc_lib_exit() The function __init ccid_initialize_builtins() references a function __exit tfrc_lib_exit(). This is often seen when error handling in the init function uses functionality in the exit path. The fix is often to remove the __exit annotation of tfrc_lib_exit() so it may be used outside an exit section. Signed-off-by: Leonardo Potenza <lpotenza@inwind.it> Acked-by: Arnaldo Carvalho de Melo <acme@redhat.com> Acked-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: Integrate the TFRC library with DCCPGerrit Renker2009-01-048-43/+16
| | | | | | | | This patch integrates the TFRC library, which is a dependency of CCID-3 (and CCID-4), with the new use of CCIDs in the DCCP module. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: Lockless integration of CCID congestion-control pluginsGerrit Renker2009-01-044-98/+25
| | | | | | | | | | | | | | | | | | | | Based on Arnaldo's earlier patch, this patch integrates the standardised CCID congestion control plugins (CCID-2 and CCID-3) of DCCP with dccp.ko: * enables a faster connection path by eliminating the need to always go through the CCID registration lock; * updates the implementation to use only a single array whose size equals the number of configured CCIDs instead of the maximum (256); * since the CCIDs are now fixed array elements, synchronization is no longer needed, simplifying use and implementation. CCID-2 is suggested as minimum for a basic DCCP implementation (RFC 4340, 10); CCID-3 is a standards-track CCID supported by RFC 4342 and RFC 5348. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
* dccp: Registration routines for changing feature valuesGerrit Renker2008-11-121-3/+3
| | | | | | | | | | | | | | Two registration routines, for SP and NN features, are provided by this patch, replacing a previous routine which was used for both feature types. These are internal-only routines and therefore start with `__feat_register'. It further exports the known limits of Sequence Window and Ack Ratio as symbolic constants. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz> Signed-off-by: David S. Miller <davem@davemloft.net>
* This reverts "Merge branch 'dccp' of git://eden-feed.erg.abdn.ac.uk/dccp_exp"Gerrit Renker2008-09-0911-953/+1116
| | | | | | as it accentally contained the wrong set of patches. These will be submitted separately. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Preventing OscillationsGerrit Renker2008-09-043-2/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | This implements [RFC 3448, 4.5], which performs congestion avoidance behaviour by reducing the transmit rate as the queueing delay (measured in terms of long-term RTT) increases. Oscillation can be turned on/off via a module option (do_osc_prev) and via sysfs (using mode 0644), the default is off. Overflow analysis: ------------------ * oscillation prevention is done after update_x(), so that t_ipi <= 64000; * hence the multiplication "t_ipi * sqrt(R_sample)" needs 64 bits; * done using u64 for sqrt_sample and explicit typecast of t_ipi; * the divisor, R_sqmean, is non-zero because oscillation prevention is first called when receiving the second feedback packet, and tfrc_scaled_rtt() > 0. A detailed discussion of the algorithm (with plots) is on http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid3/sender_notes/oscillation_prevention/ The algorithm has negative side effects: * when allowing to decrease t_ipi (leads to a large RTT) and * when using it during slow-start; both uses are therefore disabled. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
OpenPOWER on IntegriCloud