summaryrefslogtreecommitdiffstats
path: root/net/dccp/ccids/ccid3.c
Commit message (Collapse)AuthorAgeFilesLines
* 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-121-2/+1
| | | | | | | | | | | 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>
* dccp ccid-3: Remove redundant 'options_received' structGerrit Renker2010-09-211-16/+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-211-5/+4
| | | | | | | | | | | | | | 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-211-28/+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-151-43/+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-151-15/+19
| | | | | | | | | | | | | | | | | | | | | | | 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-151-11/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-301-6/+5
| | | | | | | | | | | | | | | | | | | | | | 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-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-231-12/+18
| | | | | | | | | | | | | | | 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>
* 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-3: Overhaul CCID naming convention 2/2Gerrit Renker2009-10-071-172/+149
| | | | | | | | 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>
* net-next-2.6 [PATCH 1/1] dccp: ccids whitespace-cleanup / CodingStyleGerrit Renker2009-09-141-3/+2
| | | | | | | | | | | | | | | 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: Lockless integration of CCID congestion-control pluginsGerrit Renker2009-01-041-21/+2
| | | | | | | | | | | | | | | | | | | | 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>
* This reverts "Merge branch 'dccp' of git://eden-feed.erg.abdn.ac.uk/dccp_exp"Gerrit Renker2008-09-091-301/+461
| | | | | | 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-041-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* dccp ccid-3: Simplify computing and range-checking of t_ipiGerrit Renker2008-09-041-10/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch simplifies the computation of t_ipi, avoiding expensive computations to enforce the minimum sending rate. Both RFC 3448 and rfc3448bis (revision #06), as well as RFC 4342 sec 5., require at various stages that at least one packet must be sent per t_mbi = 64 seconds. This requires frequent divisions of the type X_min = s/t_mbi, which are later converted back into an inter-packet-interval t_ipi_max = s/X_min = t_mbi. The patch removes the expensive indirection; in the unlikely case of having a sending rate less than one packet per 64 seconds, it also re-adjusts X. The following cases document conformance with RFC 3448 / rfc3448bis-06: 1) Time until receiving the first feedback packet: * if the sender has no initial RTT sample then X = s/1 Bps > s/t_mbi; * if the sender has an initial RTT sample or when the first feedback packet is received, X = W_init/R > s/t_mbi. 2) Slow-start (p == 0 and feedback packets come in): * RFC 3448 (current code) enforces a minimum of s/R > s/t_mbi; * rfc3448bis (future code) enforces an even higher minimum of W_init/R. 3) Congestion avoidance with no absence of feedback (p > 0): * when X_calc or X_recv/2 are too low, the minimum of X_min = s/t_mbi is enforced in update_x() when calling update_send_interval(); * update_send_interval() is, as before, only called when X changes (i.e. either when increasing or decreasing, not when in equilibrium). 4) Reduction of X without prior feedback or during slow-start (p==0): * both RFC 3448 and rfc3448bis here halve X directly; * the associated constraint X >= s/t_mbi is nforced here by send_interval(). 5) Reduction of X when p > 0: * X is modified indirectly via X_recv (RFC 3448) or X_recv_set (rfc3448bis); * in both cases, control goes back to section 4.3 (in both documents); * since p > 0, both documents use X = max(min(...), s/t_mbi), which is enforced in this patch by calling send_interval() from update_x(). I think that this analysis is exhaustive. Should I have forgotten a case, the worst-case consideration arises when X sinks below s/t_mbi, and is then increased back up to this minimum value. Even under this assumption, the behaviour is correct, since all lower limits of X in RFC 3448 / rfc3448bis are either equal to or greater than s/t_mbi. Note on the condition X >= s/t_mbi <==> t_ipi = s/X <= t_mbi: since X is scaled by 64, and all time units are in microseconds, the coded condition is: t_ipi = s * 64 * 10^6 usec / X <= 64 * 10^6 usec This simplifies to s / X <= 1 second <==> X * 1 second >= s > 0. (A zero `s' is not allowed by the CCID-3 code). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Measuring the packet size s with regard to rfc3448bis-06Gerrit Renker2008-09-041-12/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | rfc3448bis allows three different ways of tracking the packet size `s': 1. using the MSS/MPS (at initialisation, 4.2, and in 4.1 (1)); 2. using the average of `s' (in 4.1); 3. using the maximum of `s' (in 4.2). Instead of hard-coding a single interpretation of rfc3448bis, this implements a choice of all three alternatives and suggests the first as default, since it is the option which is most consistent with other parts of the specification. The patch further deprecates the update of t_ipi whenever `s' changes. The gains of doing this are only small since a change of s takes effect at the next instant X is updated: * when the next feedback comes in (within one RTT or less); * when the nofeedback timer expires (within at most 4 RTTs). Further, there are complications caused by updating t_ipi whenever s changes: * if t_ipi had previously been updated to effect oscillation prevention (4.5), then it is impossible to make the same adjustment to t_ipi again, thus counter-acting the algorithm; * s may be updated any time and a modification of t_ipi depends on the current state (e.g. no oscillation prevention is done in the absence of feedback); * in rev-06 of rfc3448bis, there are more possible cases, depending on whether the sender is in slow-start (t_ipi <= R/W_init), or in congestion-avoidance, limited by X_recv or the throughput equation (t_ipi <= t_mbi). Thus there are side effects of always updating t_ipi as s changes. These may not be desirable. The only case I can think of where such an update makes sense is to recompute X_calc when p > 0 and when s changes (not done by this patch). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Implement rfc3448bis change to initial-rate computationGerrit Renker2008-09-041-7/+5
| | | | | | | | | | | | | | | | | | | The patch updates CCID-3 with regard to the latest rfc3448bis-06: * in the first revisions of the draft, MSS was used for the RFC 3390 window; * then (from revision #1 to revision #2), it used the packet size `s'; * now, in this revision (and apparently final), the value is back to MSS. This change has an implication for the case when no RTT sample is available, at the time of sending the first packet: * with RTT sample, 2*MSS/RTT <= initial_rate <= 4*MSS/RTT; * without RTT sample, the initial rate is one packet (s bytes) per second (sec. 4.2), but using s instead of MSS here creates an imbalance, since this would further reduce the initial sending rate. Hence the patch uses MSS (called MPS in RFC 4340) in all places. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Update the RX history records in one placeGerrit Renker2008-09-041-26/+11
| | | | | | | | | | | | | | | This patch is a requirement for enabling ECN support later on. With that change in mind, the following preparations are done: * renamed handle_loss() into congestion_event() since it returns true when a congestion event happens (it will eventually also take care of ECN packets); * lets tfrc_rx_congestion_event() always update the RX history records, since this routine needs to be called for each non-duplicate packet anyway; * made all involved boolean-type functions to have return type `bool'; Updating the RX history records is now only necessary for the packets received up to sending the first feedback. The receiver code becomes again simpler. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Update the computation of X_recvGerrit Renker2008-09-041-40/+24
| | | | | | | | | | | | | | | | | This updates the computation of X_recv with regard to Errata 610/611 for RFC 4342 and draft rfc3448bis-06, ensuring that at least an interval of 1 RTT is used to compute X_recv. The change is wrapped into a new function ccid3_hc_rx_x_recv(). Further changes: ---------------- * feedback is not sent when no data packets arrived (bytes_recv == 0), as per rfc3448bis-06, 6.2; * take the timestamp for the feedback /after/ dccp_send_ack() returns, to avoid taking the transmission time into account (in case layer-2 is busy); * clearer handling of failure in ccid3_first_li(). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Always perform receiver RTT samplingGerrit Renker2008-09-041-29/+14
| | | | | | | | | | | | | | | | | | This updates the CCID-3 receiver in part with regard to errata 610 and 611 (http://www.rfc-editor.org/errata_list.php), which change RFC 4342 to use the Receive Rate as specified in rfc3448bis, requiring to constantly sample the RTT (or use a sender RTT). Doing this requires reusing the RX history structure after dealing with a loss. The patch does not resolve how to compute X_recv if the interval is less than 1 RTT. A FIXME has been added (and is resolved in subsequent patch). Furthermore, since this is all TFRC-based functionality, the RTT estimation is now also performed by the dccp_tfrc_lib module. This further simplifies the CCID-3 code. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Remove duplicate RX statesGerrit Renker2008-09-041-42/+5
| | | | | | | | | | | | The only state information that the CCID-3 receiver keeps is whether initial feedback has been sent or not. Further, this overlaps with use of feedback: * state == TFRC_RSTATE_NO_DATA as long as no feedback has been sent; * state == TFRC_RSTATE_DATA as soon as the first feedback has been sent. This patch reduces the duplication, by memorising the type of the last feedback. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc: Let dccp_tfrc_lib do the sampling workGerrit Renker2008-09-041-30/+8
| | | | | | | | | | | | | | | | This migrates more TFRC-related code into the dccp_tfrc_lib: * sampling of the packet size `s' (which is only needed until the first loss interval is computed (ccid3_first_li)); * updating the byte-counter `bytes_recvd' in between sending feedbacks. The result is a better separation of CCID-3 specific and TFRC specific code, which aids future integration with ECN and e.g. CCID-4. Further changes: ---------------- * replaced magic number of 536 with equivalent constant TCP_MIN_RCVMSS; (this constant is also used when no estimate for `s' is available). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc: Return type of update_i_mean is voidGerrit Renker2008-09-041-8/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This changes the return type of tfrc_lh_update_i_mean() to void, since that function returns always `false'. This is due to len = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq) + 1; if (len - (s64)cur->li_length <= 0) /* duplicate or reordered */ return 0; which means that update_i_mean can only increase the length of the open loss interval I_0, and hence the value of I_tot0 (RFC 3448, 5.4). Consequently the test `i_mean < old_i_mean' at the end of the function always evaluates to false. There is no known way by which a loss interval can suddenly become shorter, therefore the return type of the function is changed to void. (That is, under the given circumstances step (3) in RFC 3448, 6.1 will not occur.) Further changes: ---------------- * the function is now called from tfrc_rx_handle_loss, which is equivalent to the previous way of calling from rx_packet_recv (it was called whenever there was no new or pending loss, now it is also updated when there is a pending loss - this increases the accuracy a bit); * added a FIXME to possibly consider NDP counting as per RFC 4342 (this is not implemented yet). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc: Perform early loss detectionGerrit Renker2008-09-041-9/+39
| | | | | | | | | | | | | | | | This enables the TFRC code to begin loss detection (as soon as the module is loaded), using the latest updates from rfc3448bis-06, 6.3.1: * when the first data packet(s) are lost or marked, set * X_target = s/(2*R) => f(p) = s/(R * X_target) = 2, * corresponding to a loss rate of ~ 20.64%. The handle_loss() function is now called right at the begin of rx_packet_recv() and thus no longer protected against duplicates: hence a call to rx_duplicate() has been added. Such a call makes sense now, as the previous patch initialises the first entry with a sequence number of GSR. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc: Receiver history initialisation routineGerrit Renker2008-09-041-1/+1
| | | | | | | | | | | | This patch 1) separates history allocation and initialisation, to facilitate early loss detection (implemented by a subsequent patch); 2) removes duplication by using the existing tfrc_rx_hist_purge() if the allocation fails. This is now possible, since the initialisation routine 3) zeroes out the entire history before using it. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Simplified handling of TX statesGerrit Renker2008-09-041-35/+6
| | | | | | | | | | | | | | | | | | Since CCIDs are only used during the established phase of a connection, they have very little internal state; this specifically reduces to: * "no packet sent" if and only if s == 0, for the TX packet size s; * when the first packet has been sent (i.e. `s' > 0), the question is whether or not feedback has been received: - if a feedback packet is received, "feedback = yes" is set, - if the nofeedback timer expires, "feedback = no" is set. Thus the CCID only needs to remember state about whether or not feedback has been received. This is now implemented using a boolean flag, which is toggled when a feedback packet arrives or the nofeedback timer expires. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Runtime verification of timer resolutionGerrit Renker2008-09-041-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The DCCP base time resolution is 10 microseconds (RFC 4340, 13.1 ... 13.3). Using a timer with a lower resolution was found to trigger the following bug warnings/problems on high-speed networks (e.g. local loopback): * RTT samples are rounded down to 0 if below resolution; * in some cases, negative RTT samples were observed; * the CCID-3 feedback timer complains that the feedback interval is 0, since the feedback interval is in the order of 1 RTT or less and RTT measurement rounded this down to 0; On an Intel computer this will for instance happen when using a boot-time parameter of "clocksource=jiffies". The following system log messages were observed: 11:24:00 kernel: BUG: delta (0) <= 0 at ccid3_hc_rx_send_feedback() 11:26:12 kernel: BUG: delta (0) <= 0 at ccid3_hc_rx_send_feedback() 11:26:30 kernel: dccp_sample_rtt: unusable RTT sample 0, using min 11:26:30 last message repeated 5 times This patch defines a global constant for the time resolution, adds this in timer.c, and checks the available clock resolution at CCID-3 module load time. When the resolution is worse than 10 microseconds, module loading exits with a message "socket type not supported". Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Return-value convention of hc_tx_send_packet()Gerrit Renker2008-09-041-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 the maximum inter-packet gap is t_mbi = 64 sec. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Remove dead statesGerrit Renker2008-09-041-28/+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(). These two functions are part of the following call chain: * ccid_hc_{tx,rx}_exit() are called from ccid_delete() only; * ccid_delete() invokes ccid_hc_{tx,rx}_exit() in the way of a destructor: after calling ccid_hc_{tx,rx}_exit(), the CCID is released from memory; * ccid_delete() is in turn called only by ccid_hc_{tx,rx}_delete(); * ccid_hc_{tx,rx}_delete() is called only if - feature negotiation failed (dccp_feat_activate_values()), - when changing the RX/TX CCID (to eject the current CCID), - when destroying the socket (in dccp_destroy_sock()). In other words, 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 implicit when unloading the CCID. The patch removes this state, one switch-statement collapses as a result. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Unused argument in CCID tx functionGerrit Renker2008-09-041-2/+1
| | | | | | | | | | | This removes the argument `more' from ccid_hc_tx_packet_sent, since it was nowhere used in the entire code. (Anecdotally, this argument was not even used in the original KAME code where the function originally came from; compare the variable moreToSend in the freebsd61-dccp-kame-28.08.2006.patch now maintained by Emmanuel Lochin.) Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Remove redundant 'options_received' structGerrit Renker2008-09-041-16/+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 (cf. below) to ccid3_hc_tx_parse_options(). Why the fields are redundant ---------------------------- The Loss Event Rate p and the Receive Rate x_recv are initially 0 when first loading CCID-3, as ccid_new() zeroes out the entire ccid3_hc_tx_sock. When Loss Event Rate or Receive Rate options are received, they are stored by ccid3_hc_tx_parse_options() into the fields `ccid3or_loss_event_rate' and `ccid3or_receive_rate' of the sub-struct `options_received' in ccid3_hc_tx_sock. After parsing (considering only the established state - dccp_rcv_established()), the packet is passed on to ccid_hc_tx_packet_recv(). This calls the CCID-3 specific routine ccid3_hc_tx_packet_recv(), which performs the following copy operations between fields of ccid3_hc_tx_sock: * hctx->options_received.ccid3or_receive_rate is copied into hctx->x_recv, after scaling it for fixpoint arithmetic, by 2^64; * hctx->options_received.ccid3or_loss_event_rate is copied into hctx->p, considering the above special cases; in addition, a value of 0 here needs to be mapped into p=0 (when no Loss Event Rate option has been received yet). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp tfrc/ccid-3: Computing Loss Rate from Loss Event RateGerrit Renker2008-09-041-5/+4
| | | | | | | | | | | | | | | | | | | | This adds a function to take care of the following 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 the maximum of 100%; * we want 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). In the last case, the minimum-resolution value of p is returned. Furthermore, a bug in ccid3_hc_rx_getsockopt is fixed (1/0 was mapped into ~0U), which now allows to consistently print the scaled p-values as printf("Loss Event Rate = %u.%04u %%\n", rx_info.tfrcrx_p / 10000, rx_info.tfrcrx_p % 10000); Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Add packet type information to CCID-specific option parsingGerrit Renker2008-09-041-6/+8
| | | | | | | | | | | | | | | | | | | This patch ... 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. Also added documentation and made argument naming scheme consistent. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Simplify and consolidate tx_parse_optionsGerrit Renker2008-09-041-43/+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 ugly RTT-sampling history lookupGerrit Renker2008-09-041-15/+19
| | | | | | | | | | | | | | | | | | | | | | | 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: Bug fix for the inter-packet scheduling algorithmGerrit Renker2008-09-041-10/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. And hence replaced. The algorithm from RFC 3448, 4.6 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; } 1) Description of the bug ------------------------- Rescheduling requires a conversion into milliseconds, due to this call chain: * ccid3_hc_tx_send_packet() returns a timeout in milliseconds, * this value is converted by msecs_to_jiffies() in dccp_write_xmit(), * and finally used as jiffy-expires-value for 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; The bug is in artificially inflating t_delta to t_delta' = t_delta + 1000. This is unnecessarily large, a more adequate value is t_delta' = max(t_delta, 1000). 2) Consequences of using the corrected t_delta' ----------------------------------------------- Since t_delta <= t_gran/2 = 10^6/(2*HZ), we have t_delta <= 1000 as long as HZ >= 500. This means that t_delta' = max(1000, t_delta) is constant at 1000. On the other hand, when using a coarse HZ value of HZ < 500, we have three sub-cases that can all be reduced to using another constant of t_gran/2. (a) The first case arises when t_ipi > t_gran. Here t_delta' is the constant t_delta' = max(1000, t_gran/2) = t_gran/2. (b) If t_ipi <= 2000 < t_gran = 10^6/HZ usec, then t_delta = t_ipi/2 <= 1000, so that t_delta' = max(1000, t_delta) = 1000 < t_gran/2. (c) If 2000 < t_ipi <= t_gran, we have t_delta' = max(t_delta, 1000) = t_ipi/2. In the second and third cases we have delay values less than t_gran/2, which is in the order of less than or equal to half a jiffy. How these are treated depends on how fractions of a jiffy are handled: they are either always rounded down to 0, or always rounded up to 1 jiffy (assuming non-zero values). In both cases the error is on average in the order of 50%. Thus we are not increasing the error when in the second/third case we replace a value less than t_gran/2 with 0, by setting t_delta' to the constant t_gran/2. 3) Summary ---------- Fixing (1) and considering (2), 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: No more CCID control blocks in LISTEN stateGerrit Renker2008-09-041-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 CCID3), 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>
* dccp ccid-3: Remove ccid3hc{tx,rx}_ prefixesGerrit Renker2008-09-041-178/+159
| | | | | | | | | | | | | | | This patch does the same for CCID-3 as the previous patch for CCID-2: s#ccid3hctx_##g; s#ccid3hcrx_##g; plus manual editing to retain consistency. Please note: expanded the fields of the `struct tfrc_tx_info' in the hc_tx_sock, since using short #define identifiers is not a good idea. The only place where this embedded struct was used is ccid3_hc_tx_getsockopt(). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Toggle debug output without module unloadingGerrit Renker2008-09-041-1/+1
| | | | | | | | | | | | | | | | | This sets the sysfs permissions so that root can toggle the `debug' parameter available for nearly every DCCP module. This is useful since there are various module inter-dependencies. The debug flag can now be toggled at runtime using echo 1 > /sys/module/dccp/parameters/dccp_debug echo 1 > /sys/module/dccp_ccid2/parameters/ccid2_debug echo 1 > /sys/module/dccp_ccid3/parameters/ccid3_debug echo 1 > /sys/module/dccp_tfrc_lib/parameters/tfrc_debug The last is not very useful yet, since no code at the moment calls the tfrc_debug() macro. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Fix a loss detection bugGerrit Renker2008-07-131-7/+5
| | | | | | | | | | | | | | | | | | | | | | | This fixes a bug in the logic of the TFRC loss detection: * new_loss_indicated() should not be called while a loss is pending; * but the code allows this; * thus, for two subsequent gaps in the sequence space, when loss_count has not yet reached NDUPACK=3, the loss_count is falsely reduced to 1. To avoid further and similar problems, all loss handling and loss detection is now done inside tfrc_rx_hist_handle_loss(), using an appropriate routine to track new losses. Further changes: ---------------- * added a reminder that no RX history operations should be performed when rx_handle_loss() has identified a (new) loss, since the function takes care of packet reordering during loss detection; * made tfrc_rx_hist_loss_pending() bool (thanks to an earlier suggestion by Arnaldo); * removed unused functions. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Upgrade NDP count from 3 to 6 bytesGerrit Renker2008-07-131-1/+1
| | | | | | | | RFC 4340, 7.7 specifies up to 6 bytes for the NDP Count option, whereas the code is currently limited to up to 3 bytes. This seems to be a relict of an earlier draft version and is brought up to date by the patch. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Fix sparse warningsGerrit Renker2008-06-111-2/+2
| | | | | | | | | | | | | | | | | | | | | | | This patch fixes the following sparse warnings: * nested min(max()) expression: net/dccp/ccids/ccid3.c:91:21: warning: symbol '__x' shadows an earlier one net/dccp/ccids/ccid3.c:91:21: warning: symbol '__y' shadows an earlier one * Declaration of function prototypes in .c instead of .h file, resulting in "should it be static?" warnings. * Declared "struct dccpw" static (local to dccp_probe). * Disabled dccp_delayed_ack() - not fully removed due to RFC 4340, 11.3 ("Receivers SHOULD implement delayed acknowledgement timers ..."). * Used a different local variable name to avoid net/dccp/ackvec.c:293:13: warning: symbol 'state' shadows an earlier one net/dccp/ackvec.c:238:33: originally declared here * Removed unused functions `dccp_ackvector_print' and `dccp_ackvec_print'. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Bug-Fix - Zero RTT is possibleGerrit Renker2008-06-111-2/+8
| | | | | | | | | | | | | | | | | | | | | In commit $(825de27d9e40b3117b29a79d412b7a4b78c5d815) (from 27th May, commit message `dccp ccid-3: Fix "t_ipi explosion" bug'), the CCID-3 window counter computation was fixed to cope with RTTs < 4 microseconds. Such RTTs can be found e.g. when running CCID-3 over loopback. The fix removed a check against RTT < 4, but introduced a divide-by-zero bug. All steady-state RTTs in DCCP are filtered using dccp_sample_rtt(), which ensures non-zero samples. However, a zero RTT is possible on initialisation, when there is no RTT sample from the Request/Response exchange. The fix is to use the fallback-RTT from RFC 4340, 3.4. This is also better than just fixing update_win_count() since it allows other parts of the code to always assume that the RTT is non-zero during the time that the CCID is used. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
OpenPOWER on IntegriCloud