This fixes
 1) a bug in the recomputation of the sending rate by the nofeedback
    timer when no feedback at all has so far been sent by the receiver:
    min_t was used instead of max_t, which is wrong (cf. RFC 3448, p. 10);

 2) an error in the computation of larger initial windows: instead of
    min(... max()) (cf. RFC 4342, 5.), the code had used max(... max()).
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This performs two optimisations for the recomputation of the sending rate.

1) Currently the target sending rate X_calc is recalculated whenever
	a) the nofeedback timer expires, or
	b) a feedback packet is received.
   In the (a) case, recomputing X_calc is redundant, since

    * the parameters p and RTT do not change in between the
      reception of feedback packets;

    * the parameter X_recv is either modified from received
      feedback or via the nofeedback timer;

    * a test (`p == 0') in the nofeedback timer avoids using
      a stale/undefined value of X_calc if p was previously 0.

2) The nofeedback timer now only recomputes a timestamp when p == 0.
   This is according to step (4) of [RFC 3448, 4.3] and avoids
   unnecessarily determining a timestamp.

A debug statement about not updating X is also removed - it helps very
little in debugging and just clutters the logs.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch follows a suggestion by Ian McDonald and ensures that in
the current code the value of p can not exceed 100%.  Such a value is
illegal and would consequently cause a bug condition in tfrc_calc_x().

The receiver case is also tested, and a warning message is added.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

It simplifies waiting for the CCID module to signal that a packet
is ready to be sent.  Other simplifications flow on from this such as
removing constants.

As a result of this EAGAIN is not returned any more by dccp_wait_for_ccid
(which would otherwise lead to unnecessarily discarding the packet in
dccp_write_xmit).
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Replace all uses of kmem_cache_t with struct kmem_cache.

The patch was generated using the following script:

	#!/bin/sh
	#
	# Replace one string by another in all the kernel sources.
	#

	set -e

	for file in `find * -name "*.c" -o -name "*.h"|xargs grep -l $1`; do
		quilt add $file
		sed -e "1,\$s/$1/$2/g" $file >/tmp/$$
		mv /tmp/$$ $file
		quilt refresh
	done

The script was run like this

	sh replace kmem_cache_t "struct kmem_cache"
Signed-off-by: NChristoph Lameter <clameter@sgi.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

SLAB_ATOMIC is an alias of GFP_ATOMIC
Signed-off-by: NChristoph Lameter <clameter@sgi.com>
Signed-off-by: NAndrew Morton <akpm@osdl.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This replaces the linear search algorithm for reverse lookup with
binary search.

It has the advantage of better scalability: O(log2(N)) instead of O(N).
This means that the average number of iterations is reduced from 250
(linear search if each value appears equally likely) down to at most 9.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

 This patch deprecates the existing use of an arbitrary value TFRC_SMALLEST_P
 for low-threshold values of p. This avoids masking low-resolution errors.
 Instead, the code now checks against real boundaries (implemented by preceding
 patch) and provides warnings whenever a real value falls below the threshold.

 If such messages are observed, it is a better solution to take this as an
 indication that the lookup table needs to be re-engineered.

Changelog:
----------
 This patch
   * makes handling all TFRC resolution errors local to the TFRC library

   * removes unnecessary test whether X_calc is 'infinity' due to p==0 -- this
     condition is already caught by tfrc_calc_x()

   * removes setting ccid3hctx_p = TFRC_SMALLEST_P in ccid3_hc_tx_packet_recv
     since this is now done by the TFRC library

   * updates BUG_ON test in ccid3_hc_tx_no_feedback_timer to take into account
     that p now is either 0 (and then X_calc is irrelevant), or it is > 0; since
     the handling of TFRC_SMALLEST_P is now taken care of in the tfrc library

Justification:
--------------
 The TFRC code uses a lookup table which has a bounded resolution.
 The lowest possible value of the loss event rate `p' which can be
 resolved is currently 0.0001.  Substituting this lower threshold for
 p when p is less than 0.0001 results in a huge, exponentially-growing
 error.  The error can be computed by the following formula:

    (f(0.0001) - f(p))/f(p) * 100      for p < 0.0001

 Currently the solution is to use an (arbitrary) value
     TFRC_SMALLEST_P  =   40 * 1E-6   =   0.00004
 and to consider all values below this value as `virtually zero'.  Due to
 the exponentially growing resolution error, this is not a good idea, since
 it hides the fact that the table can not resolve practically occurring cases.
 Already at p == TFRC_SMALLEST_P, the error is as high as 58.19%!
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This
 * adds documentation about the lowest resolution that is possible within
   the bounds of the current lookup table
 * defines a constant TFRC_SMALLEST_P which defines this resolution
 * issues a warning if a given value of p is below resolution
 * combines two previously adjacent if-blocks of nearly identical
   structure into one

This patch does not change the algorithm as such.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

 1) For the forward X_calc lookup, it
    * protects effectively against RTT=0 (this case is possible), by
      returning the maximal lookup value instead of just setting it to 1
    * reformulates the array-bounds exceeded condition: this only happens
      if p is greater than 1E6 (due to the scaling)
    * the case of negative indices can now with certainty be excluded,
      since documentation shows that the formulas are within bounds
    * additional protection against p = 0 (would give divide-by-zero)

 2) For the reverse lookup, it warns against
    * protects against exceeding array bounds
    * now returns 0 if f(p) = 0, due to function definition
    * warns about minimal resolution error and returns the smallest table
      value instead of p=0 [this would mask congestion conditions]
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This fixes the following small error in tfrc_calc_x_reverse_lookup.

 1) The table is generated by the following equations:
	lookup[index][0] = g((index+1) * 1000000/TFRC_CALC_X_ARRSIZE);
	lookup[index][1] = g((index+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE);
    where g(q) is 1E6 * f(q/1E6)

 2) The reverse lookup assigns an entry in lookup[index][small]

 3) This index needs to match the above, i.e.
    * if small=0 then

      		p  = (index + 1) * 1000000/TFRC_CALC_X_ARRSIZE

    * if small=1 then

		p = (index+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE

These are exactly the changes that the patch makes; previously the code did
not conform to the way the lookup table was generated (this difference resulted
in a mean error of about 1.12%).
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This adds documentation for the TCP Reno throughput equation which is at
the heart of the TFRC sending rate / loss rate calculations.

It spells out precisely how the values were determined and what they mean.
The equations were derived through reverse engineering and found to be
fully accurate (verified using test programs).

This patch does not change any code.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This avoids a (harmless) warning message being printed at the DCCP server
(the receiver of a DCCP half connection).

Incoming packets are both directed to

 * ccid_hc_rx_packet_recv() for the server half
 * ccid_hc_tx_packet_recv() for the client half

The message gets printed since on a server the client half is currently not
sending data packets.
This is resolved for the moment by checking the DCCP-role first. In future
times (bidirectional DCCP connections), this test may have to be more
sophisticated.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

The main object of this patch is the following bug:
 ==> In ccid3_hc_tx_packet_recv, the parameters p and X_recv were updated
     _after_ the send rate was calculated. This is clearly an error and is
     resolved by re-ordering statements.

In addition,
  * r_sample is converted from u32 to long to check whether the time difference
    was negative (it would otherwise be converted to a large u32 value)
  * protection against RTT=0 (this is possible) is provided in a further patch
  * t_elapsed is also converted to long, to match the type of r_sample
  * adds a a more debugging information regarding current send rates
  * various trivial comment/documentation updates
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This bug resulted in ccid3_hc_tx_send_packet returning negative
delay values, which in turn triggered silently dequeueing packets in
dccp_write_xmit. As a result, only a few out of the submitted packets made
it at all onto the network.  Occasionally, when dccp_wait_for_ccid was
involved, this also triggered a bug warning since ccid3_hc_tx_send_packet
returned a negative value (which in reality was a negative delay value).

The cause for this bug lies in the comparison

 if (delay >= hctx->ccid3hctx_delta)
	return delay / 1000L;

The type of `delay' is `long', that of ccid3hctx_delta is `u32'. When comparing
negative long values against u32 values, the test returned `true' whenever delay
was smaller than 0 (meaning the packet was overdue to send).

The fix is by casting, subtracting, and then testing the difference with
regard to 0.

This has been tested and shown to work.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

The TFRC nofeedback timer normally expires after the maximum of 4
RTTs and twice the current send interval (RFC 3448, 4.3). On LANs
with a small RTT this can mean a high processing load and reduced
performance, since then the nofeedback timer is triggered very
frequently.

This patch provides a configuration option to set the bound for the
nofeedback timer, using as default 100 milliseconds.

By setting the configuration option to 0, strict RFC 3448 behaviour
can be enforced for the nofeedback timer.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch implements a suggestion by Ian McDonald and

 1) Avoids tests against negative packet lengths by using unsigned int
    for packet payload lengths in the CCID send_packet()/packet_sent() routines

 2) As a consequence, it removes an now unnecessary test with regard to `len > 0'
    in ccid3_hc_tx_packet_sent: that condition is always true, since
      * negative packet lengths are avoided
      * ccid3_hc_tx_send_packet flags an error whenever the payload length is 0.
        As a consequence, ccid3_hc_tx_packet_sent is never called as all errors
        returned by ccid_hc_tx_send_packet are caught in dccp_write_xmit

 3) Removes the third argument of ccid_hc_tx_send_packet (the `len' parameter),
    since it is currently always set to skb->len. The code is updated with regard
    to this parameter change.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This implements the larger-initial-windows feature for CCID 3, as described in
section 5 of RFC 4342. When the first feedback packet arrives, the sender can
send up to 2..4 packets per RTT, instead of just one.

The patch further
 * reduces the number of timestamping calls by passing the timestamp value
   (which is computed in one of the calling functions anyway) as argument

 * renames one constant with a very long name into one which is shorter and
   resembles the one in RFC 3448 (t_mbi)

 * simplifies some of the min_t/max_t cases where both `x', `y' have the same
   type

Commiter note: renamed TFRC_t_mbi to TFRC_T_MBI, to follow Linux coding style.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

To reflect the fact that this now is of no effect, not making apps
stop working, just be warned in the system log.
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This removes and cleans up unused variables and structures which have become
unnecessary following the introduction of the EWMA patch to automatically track
the CCID 3 receiver/sender packet sizes `s'.

It deprecates the PACKET_SIZE socket option by returning an error code and
printing a deprecation warning if an application tries to read or write this
socket option.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Problem:

This corrects the setting of the nofeedback timer with regard to RFC
3448 - previously it was not set to max(4*R, 2*s/X) as specified. Using
the maximum of 1 second as upper bound (as it was done before) can have
detrimental effects, especially if R is small.
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This is in response to a request sent earlier by Eric W. Biederman
and replaces all sysctl numbers for net.dccp.default with CTL_UNNUMBERED.

It has been tested to compile and to work.

Commiter note: I've removed the use of CTL_UNNUMBERED, not setting .ctl_name
               sets it to 0, that is the what CTL_UNNUMBERED is, reason is
               to avoid unneeded source code cluttering.
Signed-off-by: NGerrit Renker  <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch
 * removes setting t_RTO in ccid3_hc_tx_init (per [RFC 3448, 4.2], t_RTO is
   undefined until feedback has been received);

 * makes some trivial changes (updates of comments);

 * performs a small optimisation by exploiting that the feedback timeout
   uses the value of t_ipi. The way it is done is safe, because the timeouts
   appear after the changes to t_ipi, ensuring that up-to-date values are used;

 * in ccid3_hc_tx_packet_recv, moves the t_rto statement closer to the calculation
   of the next_tmout. This makes the code clearer to read and is also safe, since
   t_rto is not updated until the next call of ccid3_hc_tx_packet_recv, and is not
   read by the functions called via ccid_wait_for_ccid();

 * removes a `max' statement in sk_reset_timer, this is not needed since the timeout
   value is always greater than 1E6 microseconds.

 * adds `XXX'es to highlight that currently the nofeedback timer is set
   in a non-standard way
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch:

 * consolidates updating of parameters (t_nom, t_ipi, t_delta) which
   need to be updated at the same time, since they are inter-dependent

 * removes two inline functions which are no longer needed as a result of
   the above consolidation

 * resolves a FIXME regarding the re-calculation of t_ipi within the nofeedback
   timer, in the state where no feedback has previously been received

 * ties updating these parameters to updating the sending rate X, exploiting
   that all three parameters in turn depend on X; and using a small optimisation
   which can reduce the number of required instructions: only update the three
   parameters when X really changes
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch concerns updating the value of the nofeedback timer when no feedback
has been received so far.

Since in this case the value of R is still undefined according to [RFC 3448,
4.2], we can not perform step (3) of [RFC 3448, 4.3].  A clarification is
provided in [RFC 4342, sec. 5], which states that in these cases the nofeedback
timer (still) expires "after two seconds".

Many thanks to Ian McDonald for pointing this out and providing the
clarification.

The patch
  * implements [RFC 4342, sec. 5] with regard to the above case
  * consolidates handling timer restart by
	- adding an appropriate jump label and
	- initialising the timeout value
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This considers the  case - ACK received while no packet has been sent
so far. Resolved by printing a (rate-limited) warning message.

Further removes an unnecessary BUG_ON in ccid3_hc_tx_packet_recv,
received feedback on a terminating connection is simply ignored.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This patch removes a switch statement which is redundant since,
 * nothing is done in states TFRC_SSTATE_NO_SENT/TFRC_SSTATE_NO_FBACK
 * it is impossible that the function is called in the state TFRC_SSTATE_TERM, since
       --the function is called, in dccp_write_xmit, after ccid3_hc_tx_send_packet
       --if ccid3_hc_tx_send_packet is called in state TFRC_SSTATE_TERM, it returns
         -EINVAL, which means that ccid3_hc_tx_packet_sent will not be called
	 (compare dccp_write_xmit)
       --> therefore, this case is logically impossible
 * the remaining state is TFRC_SSTATE_FBACK which conditionally updates t_ipi, t_nom,
   and t_delta. This is a no-op, since
       --t_ipi only changes when feedback is received
       --however, when feedback arrives via ccid3_hc_tx_packet_recv, there is an identical
         code block which performs the same set of operations
       --performing the same set of operations again in ccid3_hc_tx_packet_sent therefore
         does not change anything, since between the time of receiving the last feedback
	 (and therefore update of t_ipi, t_nom, and t_delta), the value of t_ipi has not
	 changed
       --since t_ipi has not changed, the values of t_delta and t_nom also do not change,
         they depend fully on t_ipi
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This resolves an `XXX' in ccid3_hc_tx_send_packet().

The function is only called on Data and DataAck packets and returns a negative
result on zero-sized messages. This is a reasonable policy since CCID 3 is a
congestion-control module and congestion control on zero-sized Data(Ack)
packets is in a way pathological.

The patch uses a more suitable error code for this case, it returns the Posix.1
code `EBADMSG' ("Not a data message") instead of `ENOTCONN'.

As a result of ignoring zero-sized packets, a the condition for a warning
"First packet is data" in ccid3_hc_tx_packet_sent is always satisfied; this
message has been removed since it will always be printed.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This makes some logically equivalent simplifications, by replacing
rc - values plus goto's with direct return statements.
Signed-off-by: NGerrit Renker <gerrit@erg.abdn.ac.uk>
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Problem:

This patch performs a simplifying (performance) optimisation:

 In each call of the inline function ccid3_calc_new_t_ipi(), the state is
 tested against TFRC_SSTATE_NO_FBACK. This is expensive when the function
 is called very often. A simpler solution, implemented by this patch, is
 to adapt the control flow.

Background:

Problem:

Now that we can stuff bigger ack vectors into options.
Signed-off-by: NAndrea Bittau <a.bittau@cs.ucl.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Ack vectors grow proportional to the window size.  If an ack vector does not fit
into a single option, it must be spread across multiple options.  This patch
will allow for windows to grow larger.

Committer note: Simplified the patch a bit, original algorithm kept.
Signed-off-by: NAndrea Bittau <a.bittau@cs.ucl.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Commiter note:

This was split from Andrea's original patch, in the process I changed the type
of the ackvec index fields to u16 instead of to int and haven't folded
dccp_ackvec_parse with dccp_ackvec_check_rcv_ackno.

Next patch will actually do the insertion of more than one ackvec per packet,
using, initially, up to a max of 2 ackvecs as per Andrea's original patch, then
I'll work on support for larger ackvecs, be it using a sysctl or using
setsockopt.
Signed-off-by: NAndrea Bittau <a.bittau@cs.ucl.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

Commiter note: original patch was splitted.
Signed-off-by: NAndrea Bittau <a.bittau@cs.ucl.ac.uk>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This one got lost on the way from Ian to Gerrit to me, fix it.
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This removes a non-referenced variable.
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>

This makes the code of the dccp_probe module more portable.
Signed-off-by: NIan McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: NArnaldo Carvalho de Melo <acme@mandriva.com>