1. 19 Jun, 2019 1 commit
  2. 19 Oct, 2013 1 commit
  3. 11 Jul, 2012 1 commit
  4. 15 Nov, 2010 4 commits
    • Gerrit Renker's avatar
      dccp ccid-2: Separate option parsing from CCID processing · 7e87fe84
      Gerrit Renker authored
      This patch replaces an almost identical replication of code: large parts
      of dccp_parse_options() re-appeared as ccid2_ackvector() in ccid2.c.
      
      Apart from the duplication, this caused two more problems:
       1. CCIDs should not need to be concerned with parsing header options;
       2. one can not assume that Ack Vectors appear as a contiguous area within an
          skb, it is legal to insert other options and/or padding in between. The
          current code would throw an error and stop reading in such a case.
      
      Since Ack Vectors provide CCID-specific information, they are now processed
      by the CCID directly, separating this functionality from the main DCCP code.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      7e87fe84
    • Gerrit Renker's avatar
      dccp ccid-2: Remove old infrastructure · 52394eec
      Gerrit Renker authored
      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.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      52394eec
    • Gerrit Renker's avatar
      dccp ccid-2: Update code for the Ack Vector input/registration routine · 38024086
      Gerrit Renker authored
      This patch updates 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).
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      38024086
    • Gerrit Renker's avatar
      dccp ccid-2: Algorithm to update buffer state · 5753fdfe
      Gerrit Renker authored
      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).
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      5753fdfe
  5. 10 Nov, 2010 3 commits
    • Gerrit Renker's avatar
      dccp ccid-2: Implementation of circular Ack Vector buffer with overflow handling · b3d14bff
      Gerrit Renker authored
      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 length 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.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      b3d14bff
    • Gerrit Renker's avatar
      dccp ccid-2: Separate internals of Ack Vectors from option-parsing code · 7d870936
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      7d870936
    • Gerrit Renker's avatar
      dccp ccid-2: Ack Vector interface clean-up · f17a37c9
      Gerrit Renker authored
      This patch brings the Ack Vector interface up to date. Its main purpose is
      to lay the basis for the subsequent patches of this set, which will use the
      new data structure fields and routines.
      
      There are no real algorithmic changes, rather an adaptation:
      
       (1) Replaced the static Ack Vector size (2) with a #define so that it can
           be adapted (with low loss / Ack Ratio, a value of 1 works, so 2 seems
           to be sufficient for the moment) and added a solution so that computing
           the ECN nonce will continue to work - even with larger Ack Vectors.
      
       (2) Replaced the #defines for Ack Vector states with a complete enum.
      
       (3) Replaced #defines to compute Ack Vector length and state with general
           purpose routines (inlines), and updated code to use these.
      
       (4) Added a `tail' field (conversion to circular buffer in subsequent patch).
      
       (5) Updated the (outdated) documentation for Ack Vector struct.
      
       (6) All sequence number containers now trimmed to 48 bits.
      
       (7) Removal of unused bits:
           * removed dccpav_ack_nonce from struct dccp_ackvec, since this is already
             redundantly stored in the `dccpavr_ack_nonce' (of Ack Vector record);
           * removed Elapsed Time for Ack Vectors (it was nowhere used);
           * replaced semantics of dccpavr_sent_len with dccpavr_ack_runlen, since
             the code needs to be able to remember the old run length;
           * reduced the de-/allocation routines (redundant / duplicate tests).
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      f17a37c9
  6. 02 Mar, 2009 1 commit
    • Gerrit Renker's avatar
      dccp: Minimise header option overhead in setting the MPS · 361a5c1d
      Gerrit Renker authored
      This patch resolves a long-standing FIXME to dynamically update the Maximum
      Packet Size depending on actual options usage.
      
      It uses the flags set by the feature-negotiation infrastructure to compute
      the required header option size.
      
      Most options are fixed-size, a notable exception are Ack Vectors (required
      currently only by CCID-2). These can have any length between 3 and 1020
      bytes. As a result of testing, 16 bytes (2 bytes for type/length plus 14 Ack
      Vector cells) have been found to be sufficient for loss-free situations.
      
      There are currently no CCID-specific header options which may appear on data
      packets, thus it is not necessary to define a corresponding CCID field as
      suggested in the old comment.
      
      Further changes:
      ----------------
       Adjusted the type of 'cur_mps' to match the unsigned return type of the
       function.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      Acked-by: default avatarIan McDonald <ian.mcdonald@jandi.co.nz>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      361a5c1d
  7. 05 Jan, 2009 2 commits
  8. 24 Nov, 2008 1 commit
  9. 09 Sep, 2008 1 commit
  10. 04 Sep, 2008 9 commits
    • Gerrit Renker's avatar
      dccp ccid-2: Separate option parsing from CCID processing · c8bf462b
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      c8bf462b
    • Gerrit Renker's avatar
      dccp ccid-2: Remove old infrastructure · 5a577b48
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      5a577b48
    • Gerrit Renker's avatar
      dccp ccid-2: Update code for the Ack Vector input/registration routine · e28fe59f
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      e28fe59f
    • Gerrit Renker's avatar
      dccp ccid-2: Algorithm to update buffer state · 68b1de15
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      68b1de15
    • Gerrit Renker's avatar
      dccp ccid-2: Implementation of circular Ack Vector buffer with overflow handling · d7dc7e5f
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      d7dc7e5f
    • Gerrit Renker's avatar
      dccp ccid-2: Separate internals of Ack Vectors from option-parsing code · 4829007c
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      4829007c
    • Gerrit Renker's avatar
      dccp ccid-2: Ack Vector interface clean-up · ff49e270
      Gerrit Renker authored
      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: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      ff49e270
    • Gerrit Renker's avatar
      dccp: Leave headroom for options when calculating the MPS · 55ebe3ab
      Gerrit Renker authored
      The Maximum Packet Size (MPS) is of interest for applications which want
      to transfer data, so it is only relevant to the data transfer phase of a
      connection (unless one wants to send data on the DCCP-Request, but that is
      not considered here).
      
      The strategy chosen to deal with this requirement is to leave room for only 
      such options that may appear on data packets.
      
      A special consideration applies to Ack Vectors: this is purely guesswork,
      since these can have any length between 3 and 1020 bytes. The strategy
      chosen here is to subtract a configurable minimum, the value of 16 bytes
      (2 bytes for type/length plus 14 Ack Vector cells) has been found by 
      experimentatation. If people experience this as too much or too little,
      this could later be turned into a Kconfig option.	
      
      There are currently no CCID-specific header options which may appear on data
      packets, hence it is not necessary to define a corresponding CCID field.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      Acked-by: default avatarIan McDonald <ian.mcdonald@jandi.co.nz>
      55ebe3ab
    • Gerrit Renker's avatar
      dccp: Set per-connection CCIDs via socket options · fade756f
      Gerrit Renker authored
      With this patch, TX/RX CCIDs can now be changed on a per-connection basis, which
      overrides the defaults set by the global sysctl variables for TX/RX CCIDs.
      
      To make full use of this facility, the remaining patches of this patch set are
      needed, which track dependencies and activate negotiated feature values.
      
      Note on the maximum number of CCIDs that can be registered:
      -----------------------------------------------------------
      The maximum number of CCIDs that can be registered on the socket is constrained
      by the space in a Confirm/Change feature negotiation option. 
      
      The space in these in turn depends on the size of header options as defined
      in RFC 4340, 5.8. Since this is a recurring constant, it has been moved from
      ackvec.h into linux/dccp.h, clarifying its purpose.
      
      Relative to this size, the maximum number of CCID identifiers that can be 
      present in a Confirm option (which always consumes 1 byte more than a Change
      option, cf. 6.1) is 2 bytes less than the maximum TLV size: one for the
      CCID-feature-type and one for the selected value.
      Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
      fade756f
  11. 28 Jan, 2008 1 commit
  12. 20 Dec, 2007 1 commit
  13. 10 Oct, 2007 1 commit
  14. 03 Dec, 2006 2 commits
  15. 24 Oct, 2006 1 commit
  16. 22 Sep, 2006 1 commit
  17. 30 Jun, 2006 1 commit
  18. 21 Mar, 2006 3 commits
  19. 04 Jan, 2006 1 commit
  20. 08 Oct, 2005 1 commit
  21. 18 Sep, 2005 1 commit