summaryrefslogtreecommitdiffstats
path: root/net/dccp
Commit message (Collapse)AuthorAgeFilesLines
* This reverts "Merge branch 'dccp' of git://eden-feed.erg.abdn.ac.uk/dccp_exp"Gerrit Renker2008-09-0932-3861/+2786
| | | | | | 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>
* 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-042-12/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Tidy up CCID-Kconfig dependenciesGerrit Renker2008-09-041-5/+4
| | | | | | | | | | | | | | | The per-CCID menu has several dependencies on EXPERIMENTAL. These are redundant, since net/dccp/ccids/Kconfig is sourced by net/dccp/Kconfig and since the latter menu in turn asserts a dependency on EXPERIMENTAL. The patch removes the redundant dependencies as well as the repeated reference within the sub-menu. Further changes: ---------------- Two single dependencies on CCID-3 are replaced with a single enclosing `if'. 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-045-56/+40
| | | | | | | | | | | | | | | 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-043-41/+66
| | | | | | | | | | | | | | | | | 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 tfrc: Increase number of RTT samplesGerrit Renker2008-09-041-59/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This improves the receiver RTT sampling algorithm so that it tries harder to get as many RTT samples as possible. The algorithm is based the concepts presented in RFC 4340, 8.1, using timestamps and the CCVal window counter. There exist 4 cases for the CCVal difference: * == 0: less than RTT/4 passed since last packet -- unusable; * > 4: (much) more than 1 RTT has passed since last packet -- also unusable; * == 4: perfect sample (exactly one RTT has passed since last packet); * 1..3: sub-optimal sample (between RTT/4 and 3*RTT/4 has passed). In the last case the algorithm tried to optimise by storing away the candidate and then re-trying next time. The problem is that * a large number of samples is needed to smooth out the inaccuracies of the algorithm; * the sender may not be sending enough packets to warrant a "next time"; * hence it is better to use suboptimal samples whenever possible. The algorithm now stores away the current sample only if the difference is 0. Applicability and background ---------------------------- A realistic example is MP3 streaming where packets are sent at a rate of less than one packet per RTT, which means that suitable samples are absent for a very long time. The effectiveness of using suboptimal samples (with a delta between 1 and 4) was confirmed by instrumenting the algorithm with counters. The results of two 20 second test runs were: * With the old algorithm and a total of 38442 function calls, only 394 of these calls resulted in usable RTT samples (about 1%), and 378 out of these were "perfect" samples and 28013 (unused) samples had a delta of 1..3. * With the new algorithm and a total of 37057 function calls, 1702 usable RTT samples were retrieved (about 4.6%), 5 out of these were "perfect" samples. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Clamping RTT valuesGerrit Renker2008-09-042-11/+9
| | | | | | | | | | | This extracts the clamping part of dccp_sample_rtt() and makes it available to other parts of the code (as e.g. used in the next patch). Note: The function dccp_sample_rtt() now reduces to subtracting the elapsed time. This could be eliminated but would require shorter prefixes and thus is not done by this patch - maybe an idea for later. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Always perform receiver RTT samplingGerrit Renker2008-09-044-49/+73
| | | | | | | | | | | | | | | | | | 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-042-48/+13
| | | | | | | | | | | | 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-045-35/+35
| | | | | | | | | | | | | | | | 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-044-18/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-042-9/+42
| | | | | | | | | | | | | | | | 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-043-24/+32
| | | | | | | | | | | | 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 tfrc: Suppress unavoidable "below resolution" warningGerrit Renker2008-09-041-2/+10
| | | | | | | | | | | | | | | In the congestion-avoidance phase a decay of p towards 0 is natural once fewer losses are encountered. Hence the warning message "p is below resolution" is not necessary, and thus turned into a debug message by this patch. The TFRC_SMALLEST_P is needed since in theory p never actually reaches 0. When no further losses are encountered, the loss interval I_0 grows in length, causing p to decrease towards 0, causing X_calc = s/(RTT * f(p)) to increase. With the given minimum-resolution this congestion avoidance phase stops at some fixed value, an approximation formula has been added to the documentation. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Simplified handling of TX statesGerrit Renker2008-09-042-44/+8
| | | | | | | | | | | | | | | | | | 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-043-3/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 qpolicy: Parameter checking of cmsg qpolicy parametersTomasz Grobelny2008-09-043-6/+22
| | | | | | | | Ensure that cmsg->cmsg_type value is valid for qpolicy that is currently in use. Signed-off-by: Tomasz Grobelny <tomasz@grobelny.oswiecenia.net> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Policy-based packet dequeueing infrastructureTomasz Grobelny2008-09-045-8/+206
| | | | | | | | | | | | | | | | | This patch adds a generic infrastructure for policy-based dequeueing of TX packets and provides two policies: * a simple FIFO policy (which is the default) and * a priority based policy (set via socket options). Both policies honour the tx_qlen sysctl for the maximum size of the write queue (can be overridden via socket options). The priority policy uses skb->priority internally to assign an u32 priority identifier, using the same ranking as SO_PRIORITY. The skb->priority field is set to 0 when the packet leaves DCCP. The priority is supplied as ancillary data using cmsg(3), the patch also provides the requisite parsing routines. Signed-off-by: Tomasz Grobelny <tomasz@grobelny.oswiecenia.net> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Clean up slow-path input processingGerrit Renker2008-09-041-35/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch rearranges the order of statements of the slow-path input processing (i.e. any other state than OPEN), to resolve the following issues. 1. Dependencies: the order of statements now better matches RFC 4340, 8.5, i.e. step 7 is before step 9 (previously 9 was before 7), and parsing options in step 8 (which can consume resources) now comes after step 7. 2. Bug-fix: in state CLOSED, there should not be any sequence number checking or option processing. This is why the test for CLOSED has been moved after the test for LISTEN. 3. As before sequence number checks are omitted if in state LISTEN/REQUEST, due to the note underneath the table in RFC 4340, 7.5.3. 4. Packets are now passed on to Ack Vector / CCID processing only after - step 7 (receive unexpected packets), - step 9 (receive Reset), - step 13 (receive CloseReq), - step 14 (receive Close) and only if the state is PARTOPEN. This simplifies CCID processing: - in LISTEN/CLOSED the CCIDs are non-existent; - in RESPOND/REQUEST the CCIDs have not yet been negotiated; - in CLOSEREQ and active-CLOSING the node has already closed this socket; - in passive-CLOSING the client is waiting for its Reset. In the last case, RFC 4340, 8.3 leaves it open to ignore further incoming data, which is the approach taken here. As a result of (3), CCID processing is now indeed confined to OPEN/PARTOPEN states, i.e. congestion control is performed only on the flow of data packets. This avoids pathological cases of doing congestion control on those messages which set up and terminate the connection. I have done a few checks to see if this creates a problem in other parts of the code. This seems not to be the case; even if there were one, it would be better to fix it than to perform congestion control on Close/Request/Response messages. Similarly for Ack Vectors (as they depend on the negotiated CCID). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* tcp/dccp: Consolidate common code for RFC 3390 conversionGerrit Renker2008-09-041-6/+2
| | | | | | | | This patch consolidates the 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>
* dccp: Combine the functionality of enqeueing and cloningGerrit Renker2008-09-041-7/+7
| | | | | | | | | | | | | | Realising the following call pattern, * first dccp_entail() is called to enqueue a new skb and * then skb_clone() is called to transmit a clone of that skb, this patch integrates both interrelated steps into dccp_entail(). Note: the return value of skb_clone is not checked. It may be an idea to add a warning if this occurs. In both instances, however, a timer is set for retransmission, so that cloning is re-tried via dccp_retransmit_skb(). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Remove wrappers around sk_{reset,stop}_timer()Gerrit Renker2008-09-041-24/+4
| | | | | | | | | | | | | | This removes the wrappers around the sk timer functions as it makes the code clearer and not much is gained from using wrappers: the BUG_ON in start_rto_timer will never trigger since that function was called only when * the RTO timer expired (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). One further motive behind this patch is to replace 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>
* dccp ccid-2: Replace broken RTT estimator with better algorithmGerrit Renker2008-09-042-82/+107
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 - reasons for this code duplication are given below. 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>
* dccp ccid-2: Simplify dec_pipe and rearming of RTO timerGerrit Renker2008-09-041-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>
* dccp ccid-2: Remove redundant sanity testsGerrit Renker2008-09-041-51/+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>
* dccp ccid-2: Stop pollingGerrit Renker2008-09-042-8/+18
| | | | | | | This updates CCID2 to use the CCID dequeuing mechanism, converting from previous constant-polling to a now event-driven mechanism. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Refine the wait-for-ccid mechanismGerrit Renker2008-09-044-53/+82
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This extends the existing wait-for-ccid routine so that it may be used with different types of CCID. It further addresses the problems listed below. The code looks if the write queue is non-empty and grants the TX CCID up to `timeout' jiffies to drain the queue. It will instead purge that queue if * the delay suggested by the CCID exceeds the time budget; * a socket error occurred while waiting for the CCID; * there is a signal pending (eg. annoyed user pressed Control-C); * the CCID does not support delays (we don't know how long it will take). D e t a i l s [can be removed] ------------------------------- DCCP's sending mechanism functions a bit like non-blocking I/O: dccp_sendmsg() will enqueue up to net.dccp.default.tx_qlen packets (default=5), without waiting for them to be released to the network. Rate-based CCIDs, such as CCID3/4, can impose sending delays of up to maximally 64 seconds (t_mbi in RFC 3448). Hence the write queue may still contain packets when the application closes. Since the write queue is congestion-controlled by the CCID, draining the queue is also under control of the CCID. There are several problems that needed to be addressed: 1) The queue-drain mechanism only works with rate-based CCIDs. If CCID2 for example has a full TX queue and becomes network-limited just as the application wants to close, then waiting for CCID2 to become unblocked could lead to an indefinite delay (i.e., application "hangs"). 2) Since each TX CCID in turn uses a feedback mechanism, there may be changes in its sending policy while the queue is being drained. This can lead to further delays during which the application will not be able to terminate. 3) The minimum wait time for CCID3/4 can be expected to be the queue length times the current inter-packet delay. For example if tx_qlen=100 and a delay of 15 ms is used for each packet, then the application would have to wait for a minimum of 1.5 seconds before being allowed to exit. 4) There is no way for the user/application to control this behaviour. It would be good to use the timeout argument of dccp_close() as an upper bound. Then the maximum time that an application is willing to wait for its CCIDs to can be set via the SO_LINGER option. These problems are addressed by giving the CCID a grace period of up to the `timeout' value. The wait-for-ccid function is, as before, used when the application (a) has read all the data in its receive buffer and (b) if SO_LINGER was set with a non-zero linger time, or (c) the socket is either in the OPEN (active close) or in the PASSIVE_CLOSEREQ state (client application closes after receiving CloseReq). In addition, there is a catch-all case by calling __skb_queue_purge() after waiting for the CCID. This is necessary since the write queue may still have data when (a) the host has been passively-closed, (b) abnormal termination (unread data, zero linger time), (c) wait-for-ccid could not finish within the given time limit. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Extend CCID packet dequeueing interfaceGerrit Renker2008-09-042-59/+95
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This extends the packet dequeuing interface of dccp_write_xmit() to allow 1. CCIDs to take care of timing when the next packet may be sent; 2. delayed sending (as before, with an inter-packet gap up to 65.535 seconds). The main purpose is to take CCID2 out of its polling mode (when it is network- limited, it tries every millisecond to send, without interruption). The interface can also be used to support other CCIDs. The mode of operation for (2) is as follows: * new packet is enqueued via dccp_sendmsg() => dccp_write_xmit(), * ccid_hc_tx_send_packet() detects that it may not send (e.g. window full), * it signals this condition via `CCID_PACKET_WILL_DEQUEUE_LATER', * dccp_write_xmit() returns without further action; * after some time the wait-condition for CCID becomes true, * that CCID schedules the tasklet, * tasklet function calls ccid_hc_tx_send_packet() via dccp_write_xmit(), * since the wait-condition is now true, ccid_hc_tx_packet() returns "send now", * packet is sent, and possibly more (since dccp_write_xmit() loops). Code reuse: the taskled function calls dccp_write_xmit(), the timer function reduces to a wrapper around the same code. If the tasklet finds that the socket is locked, it re-schedules the tasklet function (not the tasklet) after one jiffy. Changed DCCP_BUG to dccp_pr_debug when transmit_skb returns an error (e.g. when a local qdisc is used, NET_XMIT_DROP=1 can be returned for many packets). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Return-value convention of hc_tx_send_packet()Gerrit Renker2008-09-042-9/+37
| | | | | | | | | | | | | | | | | | 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-2: Separate option parsing from CCID processingGerrit Renker2008-09-045-100/+101
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. The patch provides a new data structure and associated list housekeeping. Only small changes were necessary to integrate with CCID-2: data structure initialisation, adapt list traversal routine, and add call to the provided cleanup routine. The latter also lead to fixing the following BUG: CCID-2 so far ignored Ack Vectors on all packets other than Ack/DataAck, which is incorrect, since Ack Vectors can be present on any packet that has an Ack field. Details: -------- * received Ack Vectors are parsed by dccp_parse_options() alone, which passes the result on to the CCID-specific routine ccid_hc_tx_parse_options(); * CCIDs interested in using/decoding Ack Vector information will add code to fetch parsed Ack Vectors via this interface; * a data structure, `struct dccp_ackvec_parsed' is provided as interface; * this structure arranges Ack Vectors of the same skb into a FIFO order; * a doubly-linked list is used to keep the required FIFO code small. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Remove old infrastructureGerrit Renker2008-09-045-336/+3
| | | | | | | | | | | | | | | | This removes * functions for which updates have been provided in the preceding patches and * the @av_vec_len field - it is no longer necessary since the buffer length is now always computed dynamically; * conditional debugging code (CONFIG_IP_DCCP_ACKVEC). The reason for removing the conditional debugging code is that Ack Vectors are an almost inevitable necessity - RFC 4341 says that for CCID-2, Ack Vectors must be used. Furthermore, the code would be only interesting for coding - after some extensive testing with this patch set, having the debug code around is no longer of real help. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Schedule Sync as out-of-band mechanismGerrit Renker2008-09-042-4/+28
| | | | | | | | | | | | | | | | | | | | | | | | The problem with Ack Vectors is that i) their length is variable and can in principle grow quite large, ii) it is hard to predict exactly how large they will be. Due to the second point it seems not a good idea to reduce the MPS; in particular when on average there is enough room for the Ack Vector and an increase in length is momentarily due to some burst loss, after which the Ack Vector returns to its normal/average length. The solution taken by this patch is to subtract a minimum-expected Ack Vector length from the MPS (previous patch), and to defer any larger Ack Vectors onto a separate Sync - but only if indeed there is no space left on the skb. This patch provides the infrastructure to schedule Sync-packets for transporting (urgent) out-of-band data. Its signalling is quicker than scheduling an Ack, since it does not need to wait for new application data. It can thus serve other parts of the DCCP code as well. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Consolidate Ack-Vector processing within main DCCP moduleGerrit Renker2008-09-041-22/+9
| | | | | | | | | | | | This aggregates Ack Vector processing (handling input and clearing old state) into one function, for the following reasons and benefits: * all Ack Vector-specific processing is now in one place; * duplicated code is removed; * ensuring sanity: from an Ack Vector point of view, it is better to clear the old state first before entering new state; * Ack Event handling happens mostly within the CCIDs, not the main DCCP module. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Update code for the Ack Vector input/registration routineGerrit Renker2008-09-042-0/+159
| | | | | | | | | | | | | | | | | | | | | | This patch uupdates the code which registers new packets as received, using the new circular buffer interface. It contributes a new algorithm which * supports both tail/head pointers and buffer wrap-around and * deals with overflow (head/tail move in lock-step). The updated code is also partioned differently, into 1. dealing with the empty buffer, 2. adding new packets into non-empty buffer, 3. reserving space when encountering a `hole' in the sequence space, 4. updating old state and deciding when old state is irrelevant. Protection against large burst losses: With regard to (3), it is too costly to reserve space when there are large bursts of losses. When bursts get too large, the code does no longer reserve space and just fills in cells normally. This measure reduces space consumption by a factor of 63. The code reuses in part the previous implementation by Arnaldo de Melo. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Algorithm to update buffer stateGerrit Renker2008-09-044-6/+98
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This provides a routine to consistently update the buffer state when the peer acknowledges receipt of Ack Vectors; updating state in the list of Ack Vectors as well as in the circular buffer. While based on RFC 4340, several additional (and necessary) precautions were added to protect the consistency of the buffer state. These additions are essential, since analysis and experience showed that the basic algorithm was insufficient for this task (which lead to problems that were hard to debug). The algorithm now * deals with HC-sender acknowledging to HC-receiver and vice versa, * keeps track of the last unacknowledged but received seqno in tail_ackno, * has special cases to reset the overflow condition when appropriate, * is protected against receiving older information (would mess up buffer state). Note: The older code performed an unnecessary step, where the sender cleared Ack Vector state by parsing the Ack Vector received by the HC-receiver. Doing this was entirely redundant, since * the receiver always puts the full acknowledgment window (groups 2,3 in 11.4.2) into the Ack Vectors it sends; hence the HC-receiver is only interested in the highest state that the HC-sender received; * this means that the acknowledgment number on the (Data)Ack from the HC-sender is sufficient; and work done in parsing earlier state is not necessary, since the later state subsumes the earlier one (see also RFC 4340, A.4). This older interface (dccp_ackvec_parse()) is therefore removed. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Implementation of circular Ack Vector buffer with overflow handlingGerrit Renker2008-09-044-16/+56
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This completes the implementation of a circular buffer for Ack Vectors, by extending the current (linear array-based) implementation. The changes are: (a) An `overflow' flag to deal with the case of overflow. As before, dynamic growth of the buffer will not be supported; but code will be added to deal robustly with overflowing Ack Vector buffers. (b) A `tail_seqno' field. When naively implementing the algorithm of Appendix A in RFC 4340, problems arise whenever subsequent Ack Vector records overlap, which can bring the entire run length calculation completely out of synch. (This is documented on http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\ ack_vectors/tracking_tail_ackno/ .) (c) The buffer lengthi is now computed dynamically (i.e. current fill level), as the span between head to tail. As a result, dccp_ackvec_pending() is now simpler - the #ifdef is no longer necessary since buf_empty is always true when IP_DCCP_ACKVEC is not configured. Note on overflow handling: ------------------------- The Ack Vector code previously simply started to drop packets when the Ack Vector buffer overflowed. This means that the userspace application will not be able to receive, only because of an Ack Vector storage problem. Furthermore, overflow may be transient, so that applications may later recover from the overflow. Recovering from dropped packets is more difficult (e.g. video key frames). Hence the patch uses a different policy: when the buffer overflows, the oldest entries are subsequently overwritten. This has a higher chance of recovery. Details are on http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ack_vectors/ Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Separate internals of Ack Vectors from option-parsing codeGerrit Renker2008-09-043-85/+80
| | | | | | | | | | | This patch * separates Ack Vector housekeeping code from option-insertion code; * shifts option-specific code from ackvec.c into options.c; * introduces a dedicated routine to take care of the Ack Vector records; * simplifies the dccp_ackvec_insert_avr() routine: the BUG_ON was redundant, since the list is automatically arranged in descending order of ack_seqno. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-2: Ack Vector interface clean-upGerrit Renker2008-09-044-173/+127
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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). Justification for removing Elapsed Time information [can be removed]: --------------------------------------------------------------------- 1. The Elapsed Time information for Ack Vectors was nowhere used in the code. 2. DCCP does not implement rate-based pacing of acknowledgments. The only recommendation for always including Elapsed Time is in section 11.3 of RFC 4340: "Receivers that rate-pace acknowledgements SHOULD [...] include Elapsed Time options". But such is not the case here. 3. It does not really improve estimation accuracy. The Elapsed Time field only records the time between the arrival of the last acknowledgeable packet and the time the Ack Vector is sent out. Since Linux does not (yet) implement delayed Acks, the time difference will typically be small, since often the arrival of a data packet triggers sending feedback at the HC-receiver. Justification for changes in de-/allocation routines [can be removed]: ---------------------------------------------------------------------- * INIT_LIST_HEAD in dccp_ackvec_record_new was redundant, since the list pointers were later overwritten when the node was added via list_add(); * dccp_ackvec_record_new() was called in a single place only; * calls to list_del_init() before calling dccp_ackvec_record_delete() were redundant, since subsequently the entire element was k-freed; * since all calls to dccp_ackvec_record_delete() were preceded to a call to list_del_init(), the WARN_ON test would never evaluate to true; * since all calls to dccp_ackvec_record_delete() were made from within list_for_each_entry_safe(), the test for avr == NULL was redundant; * list_empty() in ackvec_free was redundant, since the same condition is embedded in the loop condition of the subsequent list_for_each_entry_safe(). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Reduce noise in output and convert to ktime_tGerrit Renker2008-09-041-41/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fixes the problem that dccp_probe output can grow quite large without apparent benefit (many identical data points), creating huge files (up to over one Gigabyte for a few minutes' test run) which are very hard to post-process (in one instance it got so bad that gnuplot ate up all memory plus swap). The cause for the problem is that the kprobe is inserted into dccp_sendmsg(), which can be called in a polling-mode (whenever the TX queue is full due to congestion-control issues, EAGAIN is returned). This creates many very similar data points, i.e. the increase of processing time does not increase the quality/information of the probe output. The fix is to attach the probe to a different function -- write_xmit was chosen since it gets called continually (both via userspace and timer); an input-path function would stop sampling as soon as the other end stops sending feedback. For comparison the output file sizes for the same 20 second test run over a lossy link: * before / without patch: 118 Megabytes * after / with patch: 1.2 Megabytes and there was much less noise in the output. To allow backward compatibility with scripts that people use, the now-unused `size' field in the output has been replaced with the CCID identifier. This also serves for future compatibility - support for CCID2 is work in progress (depends on the still unfinished SRTT/RTTVAR updates). While at it, the update to ktime_t was also performed. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
* dccp: Merge now-reduced connect_init() functionGerrit Renker2008-09-041-13/+5
| | | | | | | | After moving the assignment of GAR/ISS from dccp_connect_init() to dccp_transmit_skb(), the former function becomes very small, so that a merger with dccp_connect() suggests itself. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Fix the adjustments to AWL and SWLGerrit Renker2008-09-043-33/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fixes a problem and a potential loophole with regard to seqno/ackno validity: the problem is that the initial adjustments to AWL/SWL were only performed at the begin of the connection, during the handshake. Since the Sequence Window feature is always greater than Wmin=32 (7.5.2), it is however necessary to perform these adjustments at least for the first W/W' (variables as per 7.5.1) packets in the lifetime of a connection. This requirement is complicated by the fact that W/W' can change at any time during the lifetime of a connection. Therefore the consequence is to perform this safety check each time SWL/AWL are updated. A second problem solved by this patch is that the remote/local Sequence Window feature values (which set the bounds for AWL/SWL/SWH) are undefined until the feature negotiation has completed. During the initial handshake we have more stringent sequence number protection, the changes added by this patch effect that {A,S}W{L,H} are within the correct bounds at the instant that feature negotiation completes (since the SeqWin feature activation handlers call dccp_update_gsr/gss()). A detailed rationale is below -- can be removed from the commit message. 1. Server sequence number checks during initial handshake --------------------------------------------------------- The server can not use the fields of the listening socket for seqno/ackno checks and thus needs to store all relevant information on a per-connection basis on the dccp_request socket. This is a size-constrained structure and has currently only ISS (dreq_iss) and ISR (dreq_isr) defined. Adding further fields (SW{L,H}, AW{L,H}) would increase the size of the struct and it is questionable whether this will have any practical gain. The currently implemented solution is as follows. * receiving first Request: dccp_v{4,6}_conn_request sets ISR := P.seqno, ISS := dccp_v{4,6}_init_sequence() * sending first Response: dccp_v{4,6}_send_response via dccp_make_response() sets P.seqno := ISS, sets P.ackno := ISR * receiving retransmitted Request: dccp_check_req() overrides ISR := P.seqno * answering retransmitted Request: dccp_make_response() sets ISS += 1, otherwise as per first Response * completing the handshake: succeeds in dccp_check_req() for the first Ack where P.ackno == ISS (P.seqno is not tested) * creating child socket: ISS, ISR are copied from the request_sock This solution will succeed whenever the server can receive the Request and the subsequent Ack in succession, without retransmissions. If there is packet loss, the client needs to retransmit until this condition succeeds; it will otherwise eventually give up. Adding further fields to the request_sock could increase the robustness a bit, in that it would make possible to let a reordered Ack (from a retransmitted Response) pass. The argument against such a solution is that if the packet loss is not persistent and an Ack gets through, why not wait for the one answering the original response: if the loss is persistent, it is probably better to not start the connection in the first place. Long story short: the present design (by Arnaldo) is simple and will likely work just as well as a more complicated solution. As a consequence, {A,S}W{L,H} are not needed until the moment the request_sock is cloned into the accept queue. At that stage feature negotiation has completed, so that the values for the local and remote Sequence Window feature (7.5.2) are known, i.e. we are now in a better position to compute {A,S}W{L,H}. 2. Client sequence number checks during initial handshake --------------------------------------------------------- Until entering PARTOPEN the client does not need the adjustments, since it constrains the Ack window to the packet it sent. * sending first Request: dccp_v{4,6}_connect() choose ISS, dccp_connect() then sets GAR := ISS (as per 8.5), dccp_transmit_skb() (with the previous bug fix) sets GSS := ISS, AWL := ISS, AWH := GSS * n-th retransmitted Request (with previous patch): dccp_retransmit_skb() via timer calls dccp_transmit_skb(), which sets GSS := ISS+n and then AWL := ISS, AWH := ISS+n * receiving any Response: dccp_rcv_request_sent_state_process() -- accepts packet if AWL <= P.ackno <= AWH; -- sets GSR = ISR = P.seqno * sending the Ack completing the handshake: dccp_send_ack() calls dccp_transmit_skb(), which sets GSS += 1 and AWL := ISS, AWH := GSS Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Schedule an Ack when receiving timestampsGerrit Renker2008-09-042-1/+3
| | | | | | | | This schedules an Ack when receiving a timestamp, exploiting the existing inet_csk_schedule_ack() function, saving one case in the `dccp_ack_pending()' function. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Remove dead statesGerrit Renker2008-09-042-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(). 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 ccid-3: Remove duplicate documentationGerrit Renker2008-09-041-4/+0
| | | | | | This removes RX-socket documentation which is either duplicate or non-existent. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp: Unused argument in CCID tx functionGerrit Renker2008-09-044-7/+6
| | | | | | | | | | | 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: Replace magic CCID-specific numbers by symbolic constantsGerrit Renker2008-09-041-10/+3
| | | | | | | | | | The constants DCCPO_{MIN,MAX}_CCID_SPECIFIC are nowhere used in the code, but instead for the CCID-specific options numbers are used. This patch unifies the use of CCID-specific option numbers, by adding symbolic names reflecting the definitions in RFC 4340, 10.3. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
* dccp ccid-3: Remove redundant 'options_received' structGerrit Renker2008-09-042-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 (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>
OpenPOWER on IntegriCloud