* [DCCP] [Patch 0/10]: Finish and repair existing Ack Vector implementation
@ 2008-02-21 9:09 Gerrit Renker
2008-02-21 9:09 ` [PATCH 01/10] [ACKVEC]: Need to ignore Ack Vectors on request sockets Gerrit Renker
0 siblings, 1 reply; 11+ messages in thread
From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw)
To: acme; +Cc: dccp, netdev
This is a re-packaged resubmission (reduction from about 20 small patches) of the
Ack Vector patch set, which accomplishes two main things.
First, it completes the implementation of a circular Ack Vector buffer. So far
the buffer was implemented as a linear array which dropped packets on overflow.
Second, it makes the Ack Vector implementation workable for Ack Ratios greater
than 1. The code does not currently work when Ack Ratio is greater than 1.
The reason that existing problems were not observed is that the main module
sets Ack Ratio to 1, which in effect bypasses Ack Vectors entirely.
Several bugs with regard to a basic implementation of RFC 4340 Ack Vectors
were fixed and protections against corrupting buffer state added:
* successive overlapping Ack Vectors were corrupting buffer state;
* a protection against outdated entries was missing;
* a modification was necessary to compute ECN nonces over multiple vectors;
* reserving entries (one per packet) didn't work well with large burst losses;
A summary of the problems that were fixed and full code documentation is on
http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ack_vectors/
The code has been tested extensively and has been part of the test tree for over
two months.
Ack Vectors are a necessary requirement of CCID-2, so it expected that CCID-2
can subsequently also be improved.
Short summary
-------------
Patch # 1: Fixes an oversight: Ack Vectors need to be ignored as long as
feature-negotiation is processing.
Patch # 2: Ack Vector interface clean-up -- preparation for subsequent patches.
Patch # 3: Separates Ack Vector - specific code from option-inserting code.
Patch # 4: Completes the implementation of a fully circular Ack Vector buffer.
Patch # 5: Adds a tested algorithm to update Ack Vector buffer state.
Patch # 6: Updates and revises the way new Ack Vector information is registered.
Patch # 7: Consolidates Ack Vector processing within DCCP main module.
Patch # 8: Adds a fallback solution - scheduling a Sync when out-of-space.
Patch # 9: Removes older and now unused parts of the Ack Vector infrastructure.
Patch #10: Separates the task of parsing Ack Vectors from the CCID(-2) code.
The revised patch set has been uploaded to
git://eden-feed.erg.abdn.ac.uk/dccp_exp [dccp]
^ permalink raw reply [flat|nested] 11+ messages in thread* [PATCH 01/10] [ACKVEC]: Need to ignore Ack Vectors on request sockets 2008-02-21 9:09 [DCCP] [Patch 0/10]: Finish and repair existing Ack Vector implementation Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 02/10] [ACKVEC]: Ack Vector interface clean-up Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker This fixes an oversight from an earlier patch. The issue is that Ack Vectors must not be parsed on request sockets, since the Ack Vector feature depends on the selection of the (TX) CCID. During the initial handshake the CCIDs are undefined, and so RFC 4340, 10.3 applies: "Using CCID-specific options and feature options during a negotiation for the corresponding CCID feature is NOT RECOMMENDED [...]" Worse, it is not even possible: when the server receives the Request from the client, the CCID and Ack vector features are undefined; when the Ack finalising the 3-way hanshake arrives, the request socket has not been cloned yet into a full socket. (This order is necessary, since otherwise the newly created socket would have to be destroyed whenever an option error occurred - a malicious hacker could simply send garbage options and exploit this.) As a result, it is not feasible to parse Ack Vectors on request sockets, since their sink (the CCIDs interested in using Ack Vector information) is undefined. Hence disabled by this patch. Two further, minor changes: * replaced magic numbers for CCID-specific options with symbolic constants; * replaced local variables `idx' with computation in argument list (btw, these indices are nowhere used -- are they really still needed???). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> --- include/linux/dccp.h | 6 ++++-- net/dccp/options.c | 19 +++++++------------ 2 files changed, 11 insertions(+), 14 deletions(-) --- a/include/linux/dccp.h +++ b/include/linux/dccp.h @@ -165,8 +165,10 @@ enum { DCCPO_TIMESTAMP_ECHO = 42, DCCPO_ELAPSED_TIME = 43, DCCPO_MAX = 45, - DCCPO_MIN_CCID_SPECIFIC = 128, - DCCPO_MAX_CCID_SPECIFIC = 255, + DCCPO_MIN_RX_CCID_SPECIFIC = 128, /* from sender to receiver */ + DCCPO_MAX_RX_CCID_SPECIFIC = 191, + DCCPO_MIN_TX_CCID_SPECIFIC = 192, /* from receiver to sender */ + DCCPO_MAX_TX_CCID_SPECIFIC = 255, }; /* DCCP CCIDS */ --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -104,9 +104,10 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, * * CCID-specific options are ignored during connection setup, as * negotiation may still be in progress (see RFC 4340, 10.3). - * + * The same applies to Ack Vectors, as these depend on the CCID. */ - if (dreq != NULL && opt >= 128) + if (dreq != NULL && (opt >= DCCPO_MIN_RX_CCID_SPECIFIC || + opt == DCCPO_ACK_VECTOR_0 || opt == DCCPO_ACK_VECTOR_1)) goto ignore_option; switch (opt) { @@ -226,23 +227,17 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, dccp_pr_debug("%s rx opt: ELAPSED_TIME=%d\n", dccp_role(sk), elapsed_time); break; - case 128 ... 191: { - const u16 idx = value - options; - + case DCCPO_MIN_RX_CCID_SPECIFIC ... DCCPO_MAX_RX_CCID_SPECIFIC: if (ccid_hc_rx_parse_options(dp->dccps_hc_rx_ccid, sk, - opt, len, idx, + opt, len, value - options, value) != 0) goto out_invalid_option; - } break; - case 192 ... 255: { - const u16 idx = value - options; - + case DCCPO_MIN_TX_CCID_SPECIFIC ... DCCPO_MAX_TX_CCID_SPECIFIC: if (ccid_hc_tx_parse_options(dp->dccps_hc_tx_ccid, sk, - opt, len, idx, + opt, len, value - options, value) != 0) goto out_invalid_option; - } break; default: DCCP_CRIT("DCCP(%p): option %d(len=%d) not " ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 02/10] [ACKVEC]: Ack Vector interface clean-up 2008-02-21 9:09 ` [PATCH 01/10] [ACKVEC]: Need to ignore Ack Vectors on request sockets Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 03/10] [ACKVEC]: Separate internals of Ack Vectors from option-parsing code Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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 unused function to print Ack Vectors; * 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> --- net/dccp/ackvec.c | 205 +++++++++++++++-------------------------------- net/dccp/ackvec.h | 103 +++++++++++++----------- net/dccp/ccids/ccid2.c | 13 +-- net/dccp/input.c | 6 +- 4 files changed, 129 insertions(+), 198 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -3,83 +3,92 @@ /* * net/dccp/ackvec.h * - * An implementation of the DCCP protocol + * An implementation of Ack Vectors for the DCCP protocol + * Copyright (c) 2007 University of Aberdeen, Scotland, UK * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@mandriva.com> - * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 as * published by the Free Software Foundation. */ #include <linux/compiler.h> -#include <linux/ktime.h> #include <linux/list.h> #include <linux/types.h> /* maximum size of a single TLV-encoded option (sans type/len bytes) */ #define DCCP_SINGLE_OPT_MAXLEN 253 -/* We can spread an ack vector across multiple options */ -#define DCCP_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * 2) +/* + * Ack Vector buffer space is static, in multiples of %DCCP_SINGLE_OPT_MAXLEN, + * the maximum size of a single Ack Vector. Setting %DCCPAV_NUM_ACKVECS to 1 + * will be sufficient for most cases of low Ack Ratios, using a value of 2 gives + * more headroom if Ack Ratio is higher or when the sender acknowledges slowly. + */ +#define DCCPAV_NUM_ACKVECS 2 +#define DCCPAV_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * DCCPAV_NUM_ACKVECS) + +enum dccp_ackvec_states { + DCCPAV_RECEIVED = 0x00, + DCCPAV_ECN_MARKED = 0x40, + DCCPAV_RESERVED = 0x80, + DCCPAV_NOT_RECEIVED = 0xC0 +}; +#define DCCPAV_MAX_RUNLEN 0x3F -#define DCCP_ACKVEC_STATE_RECEIVED 0 -#define DCCP_ACKVEC_STATE_ECN_MARKED (1 << 6) -#define DCCP_ACKVEC_STATE_NOT_RECEIVED (3 << 6) +static inline u8 dccp_ackvec_runlen(const u8 *cell) +{ + return *cell & DCCPAV_MAX_RUNLEN; +} -#define DCCP_ACKVEC_STATE_MASK 0xC0 /* 11000000 */ -#define DCCP_ACKVEC_LEN_MASK 0x3F /* 00111111 */ +static inline u8 dccp_ackvec_state(const u8 *cell) +{ + return *cell & ~DCCPAV_MAX_RUNLEN; +} -/** struct dccp_ackvec - ack vector - * - * This data structure is the one defined in RFC 4340, Appendix A. - * - * @av_buf_head - circular buffer head - * @av_buf_tail - circular buffer tail - * @av_buf_ackno - ack # of the most recent packet acknowledgeable in the - * buffer (i.e. %av_buf_head) - * @av_buf_nonce - the one-bit sum of the ECN Nonces on all packets acked - * by the buffer with State 0 +/** struct dccp_ackvec - Ack Vector main data structure * - * Additionally, the HC-Receiver must keep some information about the - * Ack Vectors it has recently sent. For each packet sent carrying an - * Ack Vector, it remembers four variables: + * This implements a fixed-size circular buffer within an array and is largely + * based on Appendix A of RFC 4340. * - * @av_records - list of dccp_ackvec_record - * @av_ack_nonce - the one-bit sum of the ECN Nonces for all State 0. - * - * @av_time - the time in usecs - * @av_buf - circular buffer of acknowledgeable packets + * @av_buf: circular buffer storage area + * @av_buf_head: head index; begin of live portion in @av_buf + * @av_buf_tail: tail index; first index _after_ the live portion in @av_buf + * @av_buf_ackno: highest seqno of acknowledgeable packet recorded in @av_buf + * @av_buf_nonce: ECN nonce sums, each covering subsequent segments of up to + * %DCCP_SINGLE_OPT_MAXLEN cells in the live portion of @av_buf + * @av_records: list of %dccp_ackvec_record (Ack Vectors sent previously) + * @av_veclen: length of the live portion of @av_buf */ struct dccp_ackvec { - u64 av_buf_ackno; - struct list_head av_records; - ktime_t av_time; + u8 av_buf[DCCPAV_MAX_ACKVEC_LEN]; u16 av_buf_head; + u16 av_buf_tail; + u64 av_buf_ackno:48; + bool av_buf_nonce[DCCPAV_NUM_ACKVECS]; + struct list_head av_records; u16 av_vec_len; - u8 av_buf_nonce; - u8 av_ack_nonce; - u8 av_buf[DCCP_MAX_ACKVEC_LEN]; }; -/** struct dccp_ackvec_record - ack vector record +/** struct dccp_ackvec_record - Records information about sent Ack Vectors * - * ACK vector record as defined in Appendix A of spec. + * These list entries define the additional information which the HC-Receiver + * keeps about recently-sent Ack Vectors; again refer to RFC 4340, Appendix A. * - * The list is sorted by avr_ack_seqno + * @avr_node: the list node in @av_records + * @avr_ack_seqno: sequence number of the packet the Ack Vector was sent on + * @avr_ack_ackno: the Ack number that this record/Ack Vector refers to + * @avr_ack_ptr: pointer into @av_buf where this record starts + * @avr_ack_runlen: run length of @avr_ack_ptr at the time of sending + * @avr_ack_nonce: the sum of @av_buf_nonce's at the time this record was sent * - * @avr_node - node in av_records - * @avr_ack_seqno - sequence number of the packet this record was sent on - * @avr_ack_ackno - sequence number being acknowledged - * @avr_ack_ptr - pointer into av_buf where this record starts - * @avr_ack_nonce - av_ack_nonce at the time this record was sent - * @avr_sent_len - lenght of the record in av_buf + * The list as a whole is sorted in descending order by @avr_ack_seqno. */ struct dccp_ackvec_record { struct list_head avr_node; - u64 avr_ack_seqno; - u64 avr_ack_ackno; + u64 avr_ack_seqno:48; + u64 avr_ack_ackno:48; u16 avr_ack_ptr; - u16 avr_sent_len; - u8 avr_ack_nonce; + u8 avr_ack_runlen; + u8 avr_ack_nonce:1; }; struct sock; --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -1,7 +1,8 @@ /* * net/dccp/ackvec.c * - * An implementation of the DCCP protocol + * An implementation of Ack Vectors for the DCCP protocol + * Copyright (c) 2007 University of Aberdeen, Scotland, UK * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net> * * This program is free software; you can redistribute it and/or modify it @@ -24,24 +25,34 @@ static struct kmem_cache *dccp_ackvec_slab; static struct kmem_cache *dccp_ackvec_record_slab; -static struct dccp_ackvec_record *dccp_ackvec_record_new(void) +struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) { - struct dccp_ackvec_record *avr = - kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); + struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority); - if (avr != NULL) - INIT_LIST_HEAD(&avr->avr_node); + if (av != NULL) { + av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1; + av->av_vec_len = 0; + memset(av->av_buf_nonce, 0, sizeof(av->av_buf_nonce)); + INIT_LIST_HEAD(&av->av_records); + } + return av; +} - return avr; +static void dccp_ackvec_purge_records(struct dccp_ackvec *av) +{ + struct dccp_ackvec_record *cur, *next; + + list_for_each_entry_safe(cur, next, &av->av_records, avr_node) + kmem_cache_free(dccp_ackvec_record_slab, cur); + INIT_LIST_HEAD(&av->av_records); } -static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr) +void dccp_ackvec_free(struct dccp_ackvec *av) { - if (unlikely(avr == NULL)) - return; - /* Check if deleting a linked record */ - WARN_ON(!list_empty(&avr->avr_node)); - kmem_cache_free(dccp_ackvec_record_slab, avr); + if (likely(av != NULL)) { + dccp_ackvec_purge_records(av); + kmem_cache_free(dccp_ackvec_slab, av); + } } static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, @@ -69,24 +80,16 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; /* Figure out how many options do we need to represent the ackvec */ const u16 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); - u16 len = av->av_vec_len + 2 * nr_opts, i; - u32 elapsed_time; + u16 len = av->av_vec_len + 2 * nr_opts; + u8 i, nonce = 0; const unsigned char *tail, *from; unsigned char *to; struct dccp_ackvec_record *avr; - suseconds_t delta; if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) return -1; - delta = ktime_us_delta(ktime_get_real(), av->av_time); - elapsed_time = delta / 10; - - if (elapsed_time != 0 && - dccp_insert_option_elapsed_time(sk, skb, elapsed_time)) - return -1; - - avr = dccp_ackvec_record_new(); + avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); if (avr == NULL) return -1; @@ -95,7 +98,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) to = skb_push(skb, len); len = av->av_vec_len; from = av->av_buf + av->av_buf_head; - tail = av->av_buf + DCCP_MAX_ACKVEC_LEN; + tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; for (i = 0; i < nr_opts; ++i) { int copylen = len; @@ -103,7 +106,13 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) if (len > DCCP_SINGLE_OPT_MAXLEN) copylen = DCCP_SINGLE_OPT_MAXLEN; - *to++ = DCCPO_ACK_VECTOR_0; + /* + * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via + * its type; ack_nonce is the sum of all individual buf_nonce's. + */ + nonce ^= av->av_buf_nonce[i]; + + *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i]; *to++ = copylen + 2; /* Check if buf_head wraps */ @@ -124,75 +133,24 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) } /* - * From RFC 4340, A.2: - * - * For each acknowledgement it sends, the HC-Receiver will add an - * acknowledgement record. ack_seqno will equal the HC-Receiver - * sequence number it used for the ack packet; ack_ptr will equal - * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will - * equal buf_nonce. + * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340. */ - avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; - avr->avr_ack_ptr = av->av_buf_head; - avr->avr_ack_ackno = av->av_buf_ackno; - avr->avr_ack_nonce = av->av_buf_nonce; - avr->avr_sent_len = av->av_vec_len; + avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + avr->avr_ack_ptr = av->av_buf_head; + avr->avr_ack_ackno = av->av_buf_ackno; + avr->avr_ack_nonce = nonce; + avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head); dccp_ackvec_insert_avr(av, avr); dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " "ack_ackno=%llu\n", - dccp_role(sk), avr->avr_sent_len, + dccp_role(sk), avr->avr_ack_runlen, (unsigned long long)avr->avr_ack_seqno, (unsigned long long)avr->avr_ack_ackno); return 0; } -struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) -{ - struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority); - - if (av != NULL) { - av->av_buf_head = DCCP_MAX_ACKVEC_LEN - 1; - av->av_buf_ackno = UINT48_MAX + 1; - av->av_buf_nonce = 0; - av->av_time = ktime_set(0, 0); - av->av_vec_len = 0; - INIT_LIST_HEAD(&av->av_records); - } - - return av; -} - -void dccp_ackvec_free(struct dccp_ackvec *av) -{ - if (unlikely(av == NULL)) - return; - - if (!list_empty(&av->av_records)) { - struct dccp_ackvec_record *avr, *next; - - list_for_each_entry_safe(avr, next, &av->av_records, avr_node) { - list_del_init(&avr->avr_node); - dccp_ackvec_record_delete(avr); - } - } - - kmem_cache_free(dccp_ackvec_slab, av); -} - -static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av, - const u32 index) -{ - return av->av_buf[index] & DCCP_ACKVEC_STATE_MASK; -} - -static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av, - const u32 index) -{ - return av->av_buf[index] & DCCP_ACKVEC_LEN_MASK; -} - /* * If several packets are missing, the HC-Receiver may prefer to enter multiple * bytes with run length 0, rather than a single byte with a larger run length; @@ -205,7 +163,7 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, unsigned int gap; long new_head; - if (av->av_vec_len + packets > DCCP_MAX_ACKVEC_LEN) + if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN) return -ENOBUFS; gap = packets - 1; @@ -213,18 +171,18 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, if (new_head < 0) { if (gap > 0) { - memset(av->av_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED, + memset(av->av_buf, DCCPAV_NOT_RECEIVED, gap + new_head + 1); gap = -new_head; } - new_head += DCCP_MAX_ACKVEC_LEN; + new_head += DCCPAV_MAX_ACKVEC_LEN; } av->av_buf_head = new_head; if (gap > 0) memset(av->av_buf + av->av_buf_head + 1, - DCCP_ACKVEC_STATE_NOT_RECEIVED, gap); + DCCPAV_NOT_RECEIVED, gap); av->av_buf[av->av_buf_head] = state; av->av_vec_len += packets; @@ -237,6 +195,8 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, const u64 ackno, const u8 state) { + u8 *cur_head = av->av_buf + av->av_buf_head, + *buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; /* * Check at the right places if the buffer is full, if it is, tell the * caller to start dropping packets till the HC-Sender acks our ACK @@ -261,7 +221,7 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, /* See if this is the first ackno being inserted */ if (av->av_vec_len == 0) { - av->av_buf[av->av_buf_head] = state; + *cur_head = state; av->av_vec_len = 1; } else if (after48(ackno, av->av_buf_ackno)) { const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); @@ -270,10 +230,9 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, * Look if the state of this packet is the same as the * previous ackno and if so if we can bump the head len. */ - if (delta == 1 && - dccp_ackvec_state(av, av->av_buf_head) == state && - dccp_ackvec_len(av, av->av_buf_head) < DCCP_ACKVEC_LEN_MASK) - av->av_buf[av->av_buf_head]++; + if (delta == 1 && dccp_ackvec_state(cur_head) == state && + dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN) + *cur_head += 1; else if (dccp_ackvec_set_buf_head_state(av, delta, state)) return -ENOBUFS; } else { @@ -286,21 +245,17 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, * could reduce the complexity of this scan.) */ u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); - u32 index = av->av_buf_head; while (1) { - const u8 len = dccp_ackvec_len(av, index); - const u8 state = dccp_ackvec_state(av, index); + const u8 len = dccp_ackvec_runlen(cur_head); /* * valid packets not yet in av_buf have a reserved * entry, with a len equal to 0. */ - if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED && - len == 0 && delta == 0) { /* Found our - reserved seat! */ + if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) { dccp_pr_debug("Found %llu reserved seat!\n", (unsigned long long)ackno); - av->av_buf[index] = state; + *cur_head = state; goto out; } /* len == 0 means one packet */ @@ -308,13 +263,12 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, goto out_duplicate; delta -= len + 1; - if (++index == DCCP_MAX_ACKVEC_LEN) - index = 0; + if (++cur_head == buf_end) + cur_head = av->av_buf; } } av->av_buf_ackno = ackno; - av->av_time = ktime_get_real(); out: return 0; @@ -325,31 +279,6 @@ out_duplicate: return -EILSEQ; } -#ifdef CONFIG_IP_DCCP_DEBUG -void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len) -{ - dccp_pr_debug_cat("ACK vector len=%d, ackno=%llu |", len, - (unsigned long long)ackno); - - while (len--) { - const u8 state = (*vector & DCCP_ACKVEC_STATE_MASK) >> 6; - const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; - - dccp_pr_debug_cat("%d,%d|", state, rl); - ++vector; - } - - dccp_pr_debug_cat("\n"); -} - -void dccp_ackvec_print(const struct dccp_ackvec *av) -{ - dccp_ackvector_print(av->av_buf_ackno, - av->av_buf + av->av_buf_head, - av->av_vec_len); -} -#endif - static void dccp_ackvec_throw_record(struct dccp_ackvec *av, struct dccp_ackvec_record *avr) { @@ -359,13 +288,13 @@ static void dccp_ackvec_throw_record(struct dccp_ackvec *av, if (av->av_buf_head <= avr->avr_ack_ptr) av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; else - av->av_vec_len = DCCP_MAX_ACKVEC_LEN - 1 - + av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 - av->av_buf_head + avr->avr_ack_ptr; /* free records */ list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { - list_del_init(&avr->avr_node); - dccp_ackvec_record_delete(avr); + list_del(&avr->avr_node); + kmem_cache_free(dccp_ackvec_record_slab, avr); } } @@ -383,7 +312,7 @@ void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, if (ackno == avr->avr_ack_seqno) { dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " "ack_ackno=%llu, ACKED!\n", - dccp_role(sk), 1, + dccp_role(sk), avr->avr_ack_runlen, (unsigned long long)avr->avr_ack_seqno, (unsigned long long)avr->avr_ack_ackno); dccp_ackvec_throw_record(av, avr); @@ -413,7 +342,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, */ avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); while (i--) { - const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; + const u8 rl = dccp_ackvec_runlen(vector); u64 ackno_end_rl; dccp_set_seqno(&ackno_end_rl, *ackno - rl); @@ -430,8 +359,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, break; found: if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { - const u8 state = *vector & DCCP_ACKVEC_STATE_MASK; - if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) { + if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) { dccp_pr_debug("%s ACK vector 0, len=%d, " "ack_seqno=%llu, ack_ackno=%llu, " "ACKED!\n", @@ -474,10 +402,9 @@ int __init dccp_ackvec_init(void) if (dccp_ackvec_slab == NULL) goto out_err; - dccp_ackvec_record_slab = - kmem_cache_create("dccp_ackvec_record", - sizeof(struct dccp_ackvec_record), - 0, SLAB_HWCACHE_ALIGN, NULL); + dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record", + sizeof(struct dccp_ackvec_record), + 0, SLAB_HWCACHE_ALIGN, NULL); if (dccp_ackvec_record_slab == NULL) goto out_destroy_slab; --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -583,8 +583,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) &vector, &veclen)) != -1) { /* go through this ack vector */ while (veclen--) { - const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; - u64 ackno_end_rl = SUB48(ackno, rl); + u64 ackno_end_rl = SUB48(ackno, dccp_ackvec_runlen(vector)); ccid2_pr_debug("ackvec start:%llu end:%llu\n", (unsigned long long)ackno, @@ -607,17 +606,15 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) * run length */ while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) { - const u8 state = *vector & - DCCP_ACKVEC_STATE_MASK; + const u8 state = dccp_ackvec_state(vector); /* new packet received or marked */ - if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED && + if (state != DCCPAV_NOT_RECEIVED && !seqp->ccid2s_acked) { - if (state == - DCCP_ACKVEC_STATE_ECN_MARKED) { + if (state == DCCPAV_ECN_MARKED) ccid2_congestion_event(sk, seqp); - } else + else ccid2_new_ack(sk, seqp, &maxincr); --- a/net/dccp/input.c +++ b/net/dccp/input.c @@ -377,8 +377,7 @@ int dccp_rcv_established(struct sock *sk, struct sk_buff *skb, if (dp->dccps_hc_rx_ackvec != NULL && dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, - DCCP_SKB_CB(skb)->dccpd_seq, - DCCP_ACKVEC_STATE_RECEIVED)) + DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED)) goto discard; dccp_deliver_input_to_ccids(sk, skb); @@ -627,8 +626,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, if (dp->dccps_hc_rx_ackvec != NULL && dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, - DCCP_SKB_CB(skb)->dccpd_seq, - DCCP_ACKVEC_STATE_RECEIVED)) + DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED)) goto discard; dccp_deliver_input_to_ccids(sk, skb); ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 03/10] [ACKVEC]: Separate internals of Ack Vectors from option-parsing code 2008-02-21 9:09 ` [PATCH 02/10] [ACKVEC]: Ack Vector interface clean-up Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 04/10] [ACKVEC]: Implementation of circular Ack Vector buffer with overflow handling Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/ackvec.c | 100 +++++++++------------------------------------------ net/dccp/ackvec.h | 5 +-- net/dccp/options.c | 60 +++++++++++++++++++++++++++++++ 3 files changed, 80 insertions(+), 85 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -110,7 +110,7 @@ extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, u64 *ackno, const u8 opt, const u8 *value, const u8 len); -extern int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb); +extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); static inline int dccp_ackvec_pending(const struct dccp_ackvec *av) { @@ -153,8 +153,7 @@ static inline int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, return -1; } -static inline int dccp_insert_option_ackvec(const struct sock *sk, - const struct sk_buff *skb) +static inline int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 nonce) { return -1; } --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -428,6 +428,66 @@ static int dccp_insert_option_timestamp_echo(struct dccp_sock *dp, return 0; } +int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) +{ + struct dccp_sock *dp = dccp_sk(sk); + struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; + /* Figure out how many options do we need to represent the ackvec */ + const u16 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); + u16 len = av->av_vec_len + 2 * nr_opts; + u8 i, nonce = 0; + const unsigned char *tail, *from; + unsigned char *to; + + if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) + return -1; + + DCCP_SKB_CB(skb)->dccpd_opt_len += len; + + to = skb_push(skb, len); + len = av->av_vec_len; + from = av->av_buf + av->av_buf_head; + tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; + + for (i = 0; i < nr_opts; ++i) { + int copylen = len; + + if (len > DCCP_SINGLE_OPT_MAXLEN) + copylen = DCCP_SINGLE_OPT_MAXLEN; + + /* + * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via + * its type; ack_nonce is the sum of all individual buf_nonce's. + */ + nonce ^= av->av_buf_nonce[i]; + + *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i]; + *to++ = copylen + 2; + + /* Check if buf_head wraps */ + if (from + copylen > tail) { + const u16 tailsize = tail - from; + + memcpy(to, from, tailsize); + to += tailsize; + len -= tailsize; + copylen -= tailsize; + from = av->av_buf; + } + + memcpy(to, from, copylen); + from += copylen; + to += copylen; + len -= copylen; + } + /* + * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340. + */ + if (dccp_ackvec_update_records(av, DCCP_SKB_CB(skb)->dccpd_seq, nonce)) + return -ENOBUFS; + return 0; +} + /** * dccp_insert_option_mandatory - Mandatory option (5.8.2) * Note that since we are using skb_push, this function needs to be called --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -55,99 +55,35 @@ void dccp_ackvec_free(struct dccp_ackvec *av) } } -static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, - struct dccp_ackvec_record *avr) -{ - /* - * AVRs are sorted by seqno. Since we are sending them in order, we - * just add the AVR at the head of the list. - * -sorbo. - */ - if (!list_empty(&av->av_records)) { - const struct dccp_ackvec_record *head = - list_entry(av->av_records.next, - struct dccp_ackvec_record, - avr_node); - BUG_ON(before48(avr->avr_ack_seqno, head->avr_ack_seqno)); - } - - list_add(&avr->avr_node, &av->av_records); -} - -int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) +/** + * dccp_ackvec_update_records - Record information about sent Ack Vectors + * @av: Ack Vector records to update + * @seqno: Sequence number of the packet carrying the Ack Vector just sent + * @nonce_sum: The sum of all buffer nonces contained in the Ack Vector + */ +int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum) { - struct dccp_sock *dp = dccp_sk(sk); - struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; - /* Figure out how many options do we need to represent the ackvec */ - const u16 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); - u16 len = av->av_vec_len + 2 * nr_opts; - u8 i, nonce = 0; - const unsigned char *tail, *from; - unsigned char *to; struct dccp_ackvec_record *avr; - if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) - return -1; - avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); if (avr == NULL) - return -1; - - DCCP_SKB_CB(skb)->dccpd_opt_len += len; - - to = skb_push(skb, len); - len = av->av_vec_len; - from = av->av_buf + av->av_buf_head; - tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; - - for (i = 0; i < nr_opts; ++i) { - int copylen = len; - - if (len > DCCP_SINGLE_OPT_MAXLEN) - copylen = DCCP_SINGLE_OPT_MAXLEN; - - /* - * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via - * its type; ack_nonce is the sum of all individual buf_nonce's. - */ - nonce ^= av->av_buf_nonce[i]; - - *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i]; - *to++ = copylen + 2; - - /* Check if buf_head wraps */ - if (from + copylen > tail) { - const u16 tailsize = tail - from; - - memcpy(to, from, tailsize); - to += tailsize; - len -= tailsize; - copylen -= tailsize; - from = av->av_buf; - } - - memcpy(to, from, copylen); - from += copylen; - to += copylen; - len -= copylen; - } + return -ENOBUFS; - /* - * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340. - */ - avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + avr->avr_ack_seqno = seqno; avr->avr_ack_ptr = av->av_buf_head; avr->avr_ack_ackno = av->av_buf_ackno; - avr->avr_ack_nonce = nonce; + avr->avr_ack_nonce = nonce_sum; avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head); + /* + * Since GSS is incremented for each packet, the list is automatically + * arranged in descending order of @ack_seqno. + */ + list_add(&avr->avr_node, &av->av_records); - dccp_ackvec_insert_avr(av, avr); - - dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " - "ack_ackno=%llu\n", - dccp_role(sk), avr->avr_ack_runlen, + dccp_pr_debug("Added Vector, ack_seqno=%llu, ack_ackno=%llu (rl=%u)\n", (unsigned long long)avr->avr_ack_seqno, - (unsigned long long)avr->avr_ack_ackno); + (unsigned long long)avr->avr_ack_ackno, + avr->avr_ack_runlen); return 0; } ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 04/10] [ACKVEC]: Implementation of circular Ack Vector buffer with overflow handling 2008-02-21 9:09 ` [PATCH 03/10] [ACKVEC]: Separate internals of Ack Vectors from option-parsing code Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 05/10] [ACKVEC]: Algorithm to update buffer state Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/ackvec.c | 33 +++++++++++++++++++++++++++++++-- net/dccp/ackvec.h | 17 ++++++++++++++--- net/dccp/dccp.h | 14 +++++++------- net/dccp/options.c | 12 ++++++------ 4 files changed, 58 insertions(+), 18 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -22,6 +22,7 @@ * the maximum size of a single Ack Vector. Setting %DCCPAV_NUM_ACKVECS to 1 * will be sufficient for most cases of low Ack Ratios, using a value of 2 gives * more headroom if Ack Ratio is higher or when the sender acknowledges slowly. + * The maximum value is bounded by the u16 types for indices and functions. */ #define DCCPAV_NUM_ACKVECS 2 #define DCCPAV_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * DCCPAV_NUM_ACKVECS) @@ -53,8 +54,10 @@ static inline u8 dccp_ackvec_state(const u8 *cell) * @av_buf_head: head index; begin of live portion in @av_buf * @av_buf_tail: tail index; first index _after_ the live portion in @av_buf * @av_buf_ackno: highest seqno of acknowledgeable packet recorded in @av_buf + * @av_tail_ackno: lowest seqno of acknowledgeable packet recorded in @av_buf * @av_buf_nonce: ECN nonce sums, each covering subsequent segments of up to * %DCCP_SINGLE_OPT_MAXLEN cells in the live portion of @av_buf + * @av_overflow: if 1 then buf_head == buf_tail indicates buffer wraparound * @av_records: list of %dccp_ackvec_record (Ack Vectors sent previously) * @av_veclen: length of the live portion of @av_buf */ @@ -63,7 +66,9 @@ struct dccp_ackvec { u16 av_buf_head; u16 av_buf_tail; u64 av_buf_ackno:48; + u64 av_tail_ackno:48; bool av_buf_nonce[DCCPAV_NUM_ACKVECS]; + u8 av_overflow:1; struct list_head av_records; u16 av_vec_len; }; @@ -111,10 +116,11 @@ extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, const u8 *value, const u8 len); extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); +extern u16 dccp_ackvec_buflen(const struct dccp_ackvec *av); -static inline int dccp_ackvec_pending(const struct dccp_ackvec *av) +static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) { - return av->av_vec_len; + return av->av_overflow == 0 && av->av_buf_head == av->av_buf_tail; } #else /* CONFIG_IP_DCCP_ACKVEC */ static inline int dccp_ackvec_init(void) @@ -158,9 +164,14 @@ static inline int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 return -1; } -static inline int dccp_ackvec_pending(const struct dccp_ackvec *av) +static inline u16 dccp_ackvec_buflen(const struct dccp_ackvec *av) { return 0; } + +static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) +{ + return true; +} #endif /* CONFIG_IP_DCCP_ACKVEC */ #endif /* _ACKVEC_H */ --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -30,8 +30,8 @@ struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority); if (av != NULL) { - av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1; - av->av_vec_len = 0; + av->av_buf_head = av->av_buf_tail = DCCPAV_MAX_ACKVEC_LEN - 1; + av->av_overflow = 0; memset(av->av_buf_nonce, 0, sizeof(av->av_buf_nonce)); INIT_LIST_HEAD(&av->av_records); } @@ -75,6 +75,14 @@ int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum) avr->avr_ack_nonce = nonce_sum; avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head); /* + * When the buffer overflows, we keep no more than one record. This is + * the simplest way of disambiguating sender-Acks dating from before the + * overflow from sender-Acks which refer to after the overflow; a simple + * solution is preferable here since we are handling an exception. + */ + if (av->av_overflow) + dccp_ackvec_purge_records(av); + /* * Since GSS is incremented for each packet, the list is automatically * arranged in descending order of @ack_seqno. */ @@ -88,6 +96,27 @@ int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum) } /* + * Buffer index and length computation using modulo-buffersize arithmetic. + * Note that, as pointers move from right to left, head is `before' tail. + */ +static inline u16 dccp_ackvec_idx_add(const u16 a, const u16 b) +{ + return (a + b) % DCCPAV_MAX_ACKVEC_LEN; +} + +static inline u16 dccp_ackvec_idx_sub(const u16 a, const u16 b) +{ + return dccp_ackvec_idx_add(a, DCCPAV_MAX_ACKVEC_LEN - b); +} + +u16 dccp_ackvec_buflen(const struct dccp_ackvec *av) +{ + if (unlikely(av->av_overflow)) + return DCCPAV_MAX_ACKVEC_LEN; + return dccp_ackvec_idx_sub(av->av_buf_tail, av->av_buf_head); +} + +/* * If several packets are missing, the HC-Receiver may prefer to enter multiple * bytes with run length 0, rather than a single byte with a larger run length; * this simplifies table updates if one of the missing packets arrives. --- a/net/dccp/dccp.h +++ b/net/dccp/dccp.h @@ -428,15 +428,15 @@ static inline void dccp_schedule_ack(struct sock *sk) inet_csk_schedule_ack(sk); } +static inline int dccp_ackvec_pending(const struct sock *sk) +{ + return dccp_sk(sk)->dccps_hc_rx_ackvec != NULL && + !dccp_ackvec_is_empty(dccp_sk(sk)->dccps_hc_rx_ackvec); +} + static inline int dccp_ack_pending(const struct sock *sk) { - const struct dccp_sock *dp = dccp_sk(sk); - return -#ifdef CONFIG_IP_DCCP_ACKVEC - (dp->dccps_hc_rx_ackvec != NULL && - dccp_ackvec_pending(dp->dccps_hc_rx_ackvec)) || -#endif - inet_csk_ack_scheduled(sk); + return dccp_ackvec_pending(sk) || inet_csk_ack_scheduled(sk); } extern int dccp_feat_signal_nn_change(struct sock *sk, u8 feat, u64 nn_val); --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -432,9 +432,10 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; + const u16 buflen = dccp_ackvec_buflen(av); /* Figure out how many options do we need to represent the ackvec */ - const u16 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); - u16 len = av->av_vec_len + 2 * nr_opts; + const u16 nr_opts = DIV_ROUND_UP(buflen, DCCP_SINGLE_OPT_MAXLEN); + u16 len = buflen + 2 * nr_opts; u8 i, nonce = 0; const unsigned char *tail, *from; unsigned char *to; @@ -445,7 +446,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) DCCP_SKB_CB(skb)->dccpd_opt_len += len; to = skb_push(skb, len); - len = av->av_vec_len; + len = buflen; from = av->av_buf + av->av_buf_head; tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; @@ -583,9 +584,8 @@ int dccp_insert_options(struct sock *sk, struct sk_buff *skb) if (dccp_insert_option_timestamp(sk, skb)) return -1; - } else if (dp->dccps_hc_rx_ackvec != NULL && - dccp_ackvec_pending(dp->dccps_hc_rx_ackvec) && - dccp_insert_option_ackvec(sk, skb) ) { + } else if (dccp_ackvec_pending(sk) && + dccp_insert_option_ackvec(sk, skb)) { return -1; } } ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 05/10] [ACKVEC]: Algorithm to update buffer state 2008-02-21 9:09 ` [PATCH 04/10] [ACKVEC]: Implementation of circular Ack Vector buffer with overflow handling Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 06/10] [ACKVEC]: Update code for the Ack Vector input/registration routine Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/ackvec.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++ net/dccp/ackvec.h | 6 +++ net/dccp/input.c | 4 +- net/dccp/options.c | 12 ++----- 4 files changed, 100 insertions(+), 10 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -116,6 +116,7 @@ extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, const u8 *value, const u8 len); extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); +extern void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno); extern u16 dccp_ackvec_buflen(const struct dccp_ackvec *av); static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) @@ -147,6 +148,11 @@ static inline int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, return -1; } +static inline void dccp_ackvec_clear_state(struct dccp_ackvec *av, + const u64 ackno) +{ +} + static inline void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, const u64 ackno) { --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -95,6 +95,24 @@ int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum) return 0; } +static struct dccp_ackvec_record *dccp_ackvec_lookup(struct list_head *av_list, + const u64 ackno) +{ + struct dccp_ackvec_record *avr; + /* + * Exploit that records are inserted in descending order of sequence + * number, start with the oldest record first. If @ackno is `before' + * the earliest ack_ackno, the packet is too old to be considered. + */ + list_for_each_entry_reverse(avr, av_list, avr_node) { + if (avr->avr_ack_seqno == ackno) + return avr; + if (before48(ackno, avr->avr_ack_seqno)) + break; + } + return NULL; +} + /* * Buffer index and length computation using modulo-buffersize arithmetic. * Note that, as pointers move from right to left, head is `before' tail. @@ -359,6 +377,76 @@ int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, return 0; } +/** + * dccp_ackvec_clear_state - Perform house-keeping / garbage-collection + * This routine is called when the peer acknowledges the receipt of Ack Vectors + * up to and including @ackno. While based on on section A.3 of RFC 4340, here + * are additional precautions to prevent corrupted buffer state. In particular, + * we use tail_ackno to identify outdated records; it always marks the earliest + * packet of group (2) in 11.4.2. + */ +void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno) + { + struct dccp_ackvec_record *avr, *next; + u8 runlen_now, eff_runlen; + s64 delta; + + avr = dccp_ackvec_lookup(&av->av_records, ackno); + if (avr == NULL) + return; + /* + * Deal with outdated acknowledgments: this arises when e.g. there are + * several old records and the acks from the peer come in slowly. In + * that case we may still have records that pre-date tail_ackno. + */ + delta = dccp_delta_seqno(av->av_tail_ackno, avr->avr_ack_ackno); + if (delta < 0) + goto free_records; + /* + * Deal with overlapping Ack Vectors: don't subtract more than the + * number of packets between tail_ackno and ack_ackno. + */ + eff_runlen = delta < avr->avr_ack_runlen ? delta : avr->avr_ack_runlen; + + runlen_now = dccp_ackvec_runlen(av->av_buf + avr->avr_ack_ptr); + /* + * The run length of Ack Vector cells does not decrease over time. If + * the run length is the same as at the time the Ack Vector was sent, we + * free the ack_ptr cell. That cell can however not be freed if the run + * length has increased: in this case we need to move the tail pointer + * backwards (towards higher indices), to its next-oldest neighbour. + */ + if (runlen_now > eff_runlen) { + + av->av_buf[avr->avr_ack_ptr] -= eff_runlen + 1; + av->av_buf_tail = dccp_ackvec_idx_add(avr->avr_ack_ptr, 1); + + /* This move may not have cleared the overflow flag. */ + if (av->av_overflow) + av->av_overflow = (av->av_buf_head == av->av_buf_tail); + } else { + av->av_buf_tail = avr->avr_ack_ptr; + /* + * We have made sure that avr points to a valid cell within the + * buffer. This cell is either older than head, or equals head + * (empty buffer): in both cases we no longer have any overflow. + */ + av->av_overflow = 0; + } + + /* + * The peer has acknowledged up to and including ack_ackno. Hence the + * first packet in group (2) of 11.4.2 is the successor of ack_ackno. + */ + av->av_tail_ackno = ADD48(avr->avr_ack_ackno, 1); + +free_records: + list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { + list_del(&avr->avr_node); + kmem_cache_free(dccp_ackvec_record_slab, avr); + } +} + int __init dccp_ackvec_init(void) { dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", --- a/net/dccp/input.c +++ b/net/dccp/input.c @@ -164,8 +164,8 @@ static void dccp_event_ack_recv(struct sock *sk, struct sk_buff *skb) struct dccp_sock *dp = dccp_sk(sk); if (dp->dccps_hc_rx_ackvec != NULL) - dccp_ackvec_check_rcv_ackno(dp->dccps_hc_rx_ackvec, sk, - DCCP_SKB_CB(skb)->dccpd_ack_seq); + dccp_ackvec_clear_state(dp->dccps_hc_rx_ackvec, + DCCP_SKB_CB(skb)->dccpd_ack_seq); } static void dccp_deliver_input_to_ccids(struct sock *sk, struct sk_buff *skb) --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -139,9 +139,8 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, case DCCPO_ACK_VECTOR_1: if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */ break; - if (dp->dccps_hc_rx_ackvec != NULL && - dccp_ackvec_parse(sk, skb, &ackno, opt, value, len)) - goto out_invalid_option; + dccp_pr_debug("%s Ack Vector (len=%u)\n", dccp_role(sk), + len); break; case DCCPO_TIMESTAMP: if (len != 4) @@ -167,8 +166,7 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, } dccp_pr_debug("%s rx opt: TIMESTAMP=%u, ackno=%llu\n", dccp_role(sk), ntohl(opt_val), - (unsigned long long) - DCCP_SKB_CB(skb)->dccpd_ack_seq); + (unsigned long long)ackno); /* schedule an Ack in case this sender is quiescent */ dccp_schedule_ack(sk); break; @@ -182,9 +180,7 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, dccp_pr_debug("%s rx opt: TIMESTAMP_ECHO=%u, len=%d, " "ackno=%llu", dccp_role(sk), opt_recv->dccpor_timestamp_echo, - len + 2, - (unsigned long long) - DCCP_SKB_CB(skb)->dccpd_ack_seq); + len + 2, (unsigned long long)ackno); value += 4; ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 06/10] [ACKVEC]: Update code for the Ack Vector input/registration routine 2008-02-21 9:09 ` [PATCH 05/10] [ACKVEC]: Algorithm to update buffer state Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 07/10] [ACKVEC]: Consolidate Ack-Vector processing within main DCCP module Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/ackvec.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++++++++ net/dccp/ackvec.h | 9 +++ 2 files changed, 159 insertions(+), 0 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -27,6 +27,9 @@ #define DCCPAV_NUM_ACKVECS 2 #define DCCPAV_MAX_ACKVEC_LEN (DCCP_SINGLE_OPT_MAXLEN * DCCPAV_NUM_ACKVECS) +/* Threshold for coping with large bursts of losses */ +#define DCCPAV_BURST_THRESH (DCCPAV_MAX_ACKVEC_LEN / 8) + enum dccp_ackvec_states { DCCPAV_RECEIVED = 0x00, DCCPAV_ECN_MARKED = 0x40, @@ -115,6 +118,7 @@ extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, u64 *ackno, const u8 opt, const u8 *value, const u8 len); +extern void dccp_ackvec_input(struct dccp_ackvec *av, u64 seqno, u8 state); extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); extern void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno); extern u16 dccp_ackvec_buflen(const struct dccp_ackvec *av); @@ -142,6 +146,11 @@ static inline void dccp_ackvec_free(struct dccp_ackvec *av) { } +static inline void dccp_ackvec_input(struct dccp_ackvec *av, u64 seq, u8 state) +{ + +} + static inline int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, const u64 ackno, const u8 state) { --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -134,6 +134,156 @@ u16 dccp_ackvec_buflen(const struct dccp_ackvec *av) return dccp_ackvec_idx_sub(av->av_buf_tail, av->av_buf_head); } +/** + * dccp_ackvec_update_old - Update previous state as per RFC 4340, 11.4.1 + * @av: non-empty buffer to update + * @distance: negative or zero distance of @seqno from buf_ackno downward + * @seqno: the (old) sequence number whose record is to be updated + * @state: state in which packet carrying @seqno was received + */ +static void dccp_ackvec_update_old(struct dccp_ackvec *av, s64 distance, + u64 seqno, enum dccp_ackvec_states state) +{ + u16 ptr = av->av_buf_head; + + BUG_ON(distance > 0); + if (unlikely(dccp_ackvec_is_empty(av))) + return; + + do { + u8 runlen = dccp_ackvec_runlen(av->av_buf + ptr); + + if (distance + runlen >= 0) { + /* + * Only update the state if packet has not been received + * yet. This is OK as per the second table in RFC 4340, + * 11.4.1; i.e. here we are using the following table: + * RECEIVED + * 0 1 3 + * S +---+---+---+ + * T 0 | 0 | 0 | 0 | + * O +---+---+---+ + * R 1 | 1 | 1 | 1 | + * E +---+---+---+ + * D 3 | 0 | 1 | 3 | + * +---+---+---+ + * The "Not Received" state was set by reserve_seats(). + */ + if (av->av_buf[ptr] == DCCPAV_NOT_RECEIVED) + av->av_buf[ptr] = state; + else + dccp_pr_debug("Not changing %llu state to %u\n", + (unsigned long long)seqno, state); + break; + } + + distance += runlen + 1; + ptr = dccp_ackvec_idx_add(ptr, 1); + + } while (ptr != av->av_buf_tail); +} + +/* Mark @num entries after buf_head as "Not yet received". */ +static void dccp_ackvec_reserve_seats(struct dccp_ackvec *av, u16 num) +{ + u16 start = dccp_ackvec_idx_add(av->av_buf_head, 1), + len = DCCPAV_MAX_ACKVEC_LEN - start; + + /* check for buffer wrap-around */ + if (num > len) { + memset(av->av_buf + start, DCCPAV_NOT_RECEIVED, len); + start = 0; + num -= len; + } + if (num) + memset(av->av_buf + start, DCCPAV_NOT_RECEIVED, num); +} + +/** + * dccp_ackvec_add_new - Record one or more new entries in Ack Vector buffer + * @av: container of buffer to update (can be empty or non-empty) + * @num_packets: number of packets to register (must be >= 1) + * @seqno: sequence number of the first packet in @num_packets + * @state: state in which packet carrying @seqno was received + */ +static void dccp_ackvec_add_new(struct dccp_ackvec *av, u32 num_packets, + u64 seqno, enum dccp_ackvec_states state) +{ + u32 num_cells = num_packets; + + if (num_packets > DCCPAV_BURST_THRESH) { + u32 lost_packets = num_packets - 1; + + DCCP_WARN("Warning: large burst loss (%u)\n", lost_packets); + /* + * We received 1 packet and have a loss of size "num_packets-1" + * which we squeeze into num_cells-1 rather than reserving an + * entire byte for each lost packet. + * The reason is that the vector grows in O(burst_length); when + * it grows too large there will no room left for the payload. + * This is a trade-off: if a few packets out of the burst show + * up later, their state will not be changed; it is simply too + * costly to reshuffle/reallocate/copy the buffer each time. + * Should such problems persist, we will need to switch to a + * different underlying data structure. + */ + for (num_packets = num_cells = 1; lost_packets; ++num_cells) { + u8 len = min(lost_packets, (u32)DCCPAV_MAX_RUNLEN); + + av->av_buf_head = dccp_ackvec_idx_sub(av->av_buf_head, 1); + av->av_buf[av->av_buf_head] = DCCPAV_NOT_RECEIVED | len; + + lost_packets -= len; + } + } + + if (num_cells + dccp_ackvec_buflen(av) >= DCCPAV_MAX_ACKVEC_LEN) { + DCCP_CRIT("Ack Vector buffer overflow: dropping old entries\n"); + av->av_overflow = true; + } + + av->av_buf_head = dccp_ackvec_idx_sub(av->av_buf_head, num_packets); + if (av->av_overflow) + av->av_buf_tail = av->av_buf_head; + + av->av_buf[av->av_buf_head] = state; + av->av_buf_ackno = seqno; + + if (num_packets > 1) + dccp_ackvec_reserve_seats(av, num_packets - 1); +} + +/** + * dccp_ackvec_input - Register incoming packet in the buffer + * @av: buffer/records to update + * @seqno: sequence number to register as received + * @state: how packet with @seqno was received, one of %dccp_ackvec_states + */ +void dccp_ackvec_input(struct dccp_ackvec *av, u64 seqno, u8 state) +{ + if (dccp_ackvec_is_empty(av)) { + dccp_ackvec_add_new(av, 1, seqno, state); + av->av_tail_ackno = seqno; + + } else { + s64 num_packets = dccp_delta_seqno(av->av_buf_ackno, seqno); + u8 *current_head = av->av_buf + av->av_buf_head; + + if (num_packets == 1 && + dccp_ackvec_state(current_head) == state && + dccp_ackvec_runlen(current_head) < DCCPAV_MAX_RUNLEN) { + + *current_head += 1; + av->av_buf_ackno = seqno; + + } else if (num_packets > 0) { + dccp_ackvec_add_new(av, num_packets, seqno, state); + } else { + dccp_ackvec_update_old(av, num_packets, seqno, state); + } + } +} + /* * If several packets are missing, the HC-Receiver may prefer to enter multiple * bytes with run length 0, rather than a single byte with a larger run length; ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 07/10] [ACKVEC]: Consolidate Ack-Vector processing within main DCCP module 2008-02-21 9:09 ` [PATCH 06/10] [ACKVEC]: Update code for the Ack Vector input/registration routine Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 08/10] [ACKVEC]: Schedule SyncAck when running out of space Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/input.c | 32 ++++++++++---------------------- 1 files changed, 10 insertions(+), 22 deletions(-) --- a/net/dccp/input.c +++ b/net/dccp/input.c @@ -159,13 +159,16 @@ static void dccp_rcv_reset(struct sock *sk, struct sk_buff *skb) dccp_time_wait(sk, DCCP_TIME_WAIT, 0); } -static void dccp_event_ack_recv(struct sock *sk, struct sk_buff *skb) +static void dccp_handle_ackvec_processing(struct sock *sk, struct sk_buff *skb) { - struct dccp_sock *dp = dccp_sk(sk); + struct dccp_ackvec *av = dccp_sk(sk)->dccps_hc_rx_ackvec; + struct dccp_skb_cb *dcb = DCCP_SKB_CB(skb); - if (dp->dccps_hc_rx_ackvec != NULL) - dccp_ackvec_clear_state(dp->dccps_hc_rx_ackvec, - DCCP_SKB_CB(skb)->dccpd_ack_seq); + if (av != NULL) { + if (dcb->dccpd_ack_seq != DCCP_PKT_WITHOUT_ACK_SEQ) + dccp_ackvec_clear_state(av, dcb->dccpd_ack_seq); + dccp_ackvec_input(av, dcb->dccpd_seq, DCCPAV_RECEIVED); + } } static void dccp_deliver_input_to_ccids(struct sock *sk, struct sk_buff *skb) @@ -364,21 +367,13 @@ discard: int dccp_rcv_established(struct sock *sk, struct sk_buff *skb, const struct dccp_hdr *dh, const unsigned len) { - struct dccp_sock *dp = dccp_sk(sk); - if (dccp_check_seqno(sk, skb)) goto discard; if (dccp_parse_options(sk, NULL, skb)) goto discard; - if (DCCP_SKB_CB(skb)->dccpd_ack_seq != DCCP_PKT_WITHOUT_ACK_SEQ) - dccp_event_ack_recv(sk, skb); - - if (dp->dccps_hc_rx_ackvec != NULL && - dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, - DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED)) - goto discard; + dccp_handle_ackvec_processing(sk, skb); dccp_deliver_input_to_ccids(sk, skb); return __dccp_rcv_established(sk, skb, dh, len); @@ -621,14 +616,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, if (dccp_parse_options(sk, NULL, skb)) goto discard; - if (dcb->dccpd_ack_seq != DCCP_PKT_WITHOUT_ACK_SEQ) - dccp_event_ack_recv(sk, skb); - - if (dp->dccps_hc_rx_ackvec != NULL && - dccp_ackvec_add(dp->dccps_hc_rx_ackvec, sk, - DCCP_SKB_CB(skb)->dccpd_seq, DCCPAV_RECEIVED)) - goto discard; - + dccp_handle_ackvec_processing(sk, skb); dccp_deliver_input_to_ccids(sk, skb); } ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 08/10] [ACKVEC]: Schedule SyncAck when running out of space 2008-02-21 9:09 ` [PATCH 07/10] [ACKVEC]: Consolidate Ack-Vector processing within main DCCP module Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 09/10] [ACKVEC]: Remove old infrastructure Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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; i 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 to address the outstanding FIXME is to schedule a separate Sync when running out of space on the skb, and to log a warning into the syslog. The mechanism can also be used for other out-of-band signalling: it does quicker signalling than scheduling an Ack, since it does not need to wait for new data. Additional Note regarding MPS: ----------------------------- It is possible to lower MPS according to the average length of Ack Vectors; the following argues why this does not seem to be a good idea. When determining the average Ack Vector length, a moving-average is more useful than a normal average, since sudden peaks (burst losses) are better dampened. The Ack Vector buffer would have a field `av_avg_len' which tracks this moving average and MPS would be reduced by this value (plus 2 bytes for type/value for each full Ack Vector). However, this means that the MPS decreases in the middle of an established connection. For a user who has tuned his/her application to work with the MPS taken at the beginning of the connection this can be very counter- intuitive and annoying. (Over the long term there should be some adjustment to reduce MPS at least by a minimum when Ack Vectors are used; some applications may rely on the exact value of the MPS). Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> --- include/linux/dccp.h | 2 ++ net/dccp/options.c | 23 +++++++++++++++++++---- net/dccp/output.c | 8 ++++++++ 3 files changed, 29 insertions(+), 4 deletions(-) --- a/include/linux/dccp.h +++ b/include/linux/dccp.h @@ -475,6 +475,7 @@ struct dccp_ackvec; * @dccps_hc_rx_insert_options - receiver wants to add options when acking * @dccps_hc_tx_insert_options - sender wants to add options when sending * @dccps_server_timewait - server holds timewait state on close (RFC 4340, 8.3) + * @dccps_sync_scheduled - flag which signals "send out-of-band message soon" * @dccps_xmit_timer - timer for when CCID is not ready to send * @dccps_syn_rtt - RTT sample from Request/Response exchange (in usecs) */ @@ -515,6 +516,7 @@ struct dccp_sock { __u8 dccps_hc_rx_insert_options:1; __u8 dccps_hc_tx_insert_options:1; __u8 dccps_server_timewait:1; + __u8 dccps_sync_scheduled:1; struct timer_list dccps_xmit_timer; }; --- a/net/dccp/output.c +++ b/net/dccp/output.c @@ -290,6 +290,8 @@ void dccp_write_xmit(struct sock *sk, int block) if (err) DCCP_BUG("err=%d after ccid_hc_tx_packet_sent", err); + if (dp->dccps_sync_scheduled) + dccp_send_sync(sk, dp->dccps_gsr, DCCP_PKT_SYNC); } else { dccp_pr_debug("packet discarded due to err=%d\n", err); kfree_skb(skb); @@ -562,6 +564,12 @@ void dccp_send_sync(struct sock *sk, const u64 ackno, DCCP_SKB_CB(skb)->dccpd_type = pkt_type; DCCP_SKB_CB(skb)->dccpd_ack_seq = ackno; + /* + * Clear the flag in case the Sync was scheduled for out-of-band data, + * such as carrying a long Ack Vector. + */ + dccp_sk(sk)->dccps_sync_scheduled = 0; + dccp_transmit_skb(sk, skb); } --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -428,6 +428,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; + struct dccp_skb_cb *dcb = DCCP_SKB_CB(skb); const u16 buflen = dccp_ackvec_buflen(av); /* Figure out how many options do we need to represent the ackvec */ const u16 nr_opts = DIV_ROUND_UP(buflen, DCCP_SINGLE_OPT_MAXLEN); @@ -436,10 +437,24 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) const unsigned char *tail, *from; unsigned char *to; - if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) + if (dcb->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) { + DCCP_WARN("Lacking space for %u bytes on %s packet\n", len, + dccp_packet_name(dcb->dccpd_type)); return -1; - - DCCP_SKB_CB(skb)->dccpd_opt_len += len; + } + /* + * Since Ack Vectors are variable-length, we can not always predict + * their size. To catch exception cases where the space is running out + * on the skb, a separate Sync is scheduled to carry the Ack Vector. + */ + if (dcb->dccpd_opt_len + skb->len + len > dp->dccps_mss_cache) { + DCCP_WARN("No space left for Ack Vector (%u) on skb (%u+%u), " + "MPS=%u ==> reduce payload size?\n", len, skb->len, + dcb->dccpd_opt_len, dp->dccps_mss_cache); + dp->dccps_sync_scheduled = 1; + return 0; + } + dcb->dccpd_opt_len += len; to = skb_push(skb, len); len = buflen; @@ -480,7 +495,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) /* * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340. */ - if (dccp_ackvec_update_records(av, DCCP_SKB_CB(skb)->dccpd_seq, nonce)) + if (dccp_ackvec_update_records(av, dcb->dccpd_seq, nonce)) return -ENOBUFS; return 0; } ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 09/10] [ACKVEC]: Remove old infrastructure 2008-02-21 9:09 ` [PATCH 08/10] [ACKVEC]: Schedule SyncAck when running out of space Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 2008-02-21 9:09 ` [PATCH 10/10] [ACKVEC]: Separate option parsing from CCID processing Gerrit Renker 0 siblings, 1 reply; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/Kconfig | 3 - net/dccp/Makefile | 5 +- net/dccp/ackvec.c | 252 ------------------------------------------------ net/dccp/ackvec.h | 79 +--------------- net/dccp/ccids/Kconfig | 1 - 5 files changed, 3 insertions(+), 337 deletions(-) --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -9,19 +9,10 @@ * under the terms of the GNU General Public License as published by the * Free Software Foundation; version 2 of the License; */ - -#include "ackvec.h" #include "dccp.h" - -#include <linux/dccp.h> -#include <linux/init.h> -#include <linux/errno.h> #include <linux/kernel.h> -#include <linux/skbuff.h> #include <linux/slab.h> -#include <net/sock.h> - static struct kmem_cache *dccp_ackvec_slab; static struct kmem_cache *dccp_ackvec_record_slab; @@ -284,249 +275,6 @@ void dccp_ackvec_input(struct dccp_ackvec *av, u64 seqno, u8 state) } } -/* - * If several packets are missing, the HC-Receiver may prefer to enter multiple - * bytes with run length 0, rather than a single byte with a larger run length; - * this simplifies table updates if one of the missing packets arrives. - */ -static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, - const unsigned int packets, - const unsigned char state) -{ - unsigned int gap; - long new_head; - - if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN) - return -ENOBUFS; - - gap = packets - 1; - new_head = av->av_buf_head - packets; - - if (new_head < 0) { - if (gap > 0) { - memset(av->av_buf, DCCPAV_NOT_RECEIVED, - gap + new_head + 1); - gap = -new_head; - } - new_head += DCCPAV_MAX_ACKVEC_LEN; - } - - av->av_buf_head = new_head; - - if (gap > 0) - memset(av->av_buf + av->av_buf_head + 1, - DCCPAV_NOT_RECEIVED, gap); - - av->av_buf[av->av_buf_head] = state; - av->av_vec_len += packets; - return 0; -} - -/* - * Implements the RFC 4340, Appendix A - */ -int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, - const u64 ackno, const u8 state) -{ - u8 *cur_head = av->av_buf + av->av_buf_head, - *buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; - /* - * Check at the right places if the buffer is full, if it is, tell the - * caller to start dropping packets till the HC-Sender acks our ACK - * vectors, when we will free up space in av_buf. - * - * We may well decide to do buffer compression, etc, but for now lets - * just drop. - * - * From Appendix A.1.1 (`New Packets'): - * - * Of course, the circular buffer may overflow, either when the - * HC-Sender is sending data at a very high rate, when the - * HC-Receiver's acknowledgements are not reaching the HC-Sender, - * or when the HC-Sender is forgetting to acknowledge those acks - * (so the HC-Receiver is unable to clean up old state). In this - * case, the HC-Receiver should either compress the buffer (by - * increasing run lengths when possible), transfer its state to - * a larger buffer, or, as a last resort, drop all received - * packets, without processing them whatsoever, until its buffer - * shrinks again. - */ - - /* See if this is the first ackno being inserted */ - if (av->av_vec_len == 0) { - *cur_head = state; - av->av_vec_len = 1; - } else if (after48(ackno, av->av_buf_ackno)) { - const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); - - /* - * Look if the state of this packet is the same as the - * previous ackno and if so if we can bump the head len. - */ - if (delta == 1 && dccp_ackvec_state(cur_head) == state && - dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN) - *cur_head += 1; - else if (dccp_ackvec_set_buf_head_state(av, delta, state)) - return -ENOBUFS; - } else { - /* - * A.1.2. Old Packets - * - * When a packet with Sequence Number S <= buf_ackno - * arrives, the HC-Receiver will scan the table for - * the byte corresponding to S. (Indexing structures - * could reduce the complexity of this scan.) - */ - u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); - - while (1) { - const u8 len = dccp_ackvec_runlen(cur_head); - /* - * valid packets not yet in av_buf have a reserved - * entry, with a len equal to 0. - */ - if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) { - dccp_pr_debug("Found %llu reserved seat!\n", - (unsigned long long)ackno); - *cur_head = state; - goto out; - } - /* len == 0 means one packet */ - if (delta < len + 1) - goto out_duplicate; - - delta -= len + 1; - if (++cur_head == buf_end) - cur_head = av->av_buf; - } - } - - av->av_buf_ackno = ackno; -out: - return 0; - -out_duplicate: - /* Duplicate packet */ - dccp_pr_debug("Received a dup or already considered lost " - "packet: %llu\n", (unsigned long long)ackno); - return -EILSEQ; -} - -static void dccp_ackvec_throw_record(struct dccp_ackvec *av, - struct dccp_ackvec_record *avr) -{ - struct dccp_ackvec_record *next; - - /* sort out vector length */ - if (av->av_buf_head <= avr->avr_ack_ptr) - av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; - else - av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 - - av->av_buf_head + avr->avr_ack_ptr; - - /* free records */ - list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { - list_del(&avr->avr_node); - kmem_cache_free(dccp_ackvec_record_slab, avr); - } -} - -void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, - const u64 ackno) -{ - struct dccp_ackvec_record *avr; - - /* - * If we traverse backwards, it should be faster when we have large - * windows. We will be receiving ACKs for stuff we sent a while back - * -sorbo. - */ - list_for_each_entry_reverse(avr, &av->av_records, avr_node) { - if (ackno == avr->avr_ack_seqno) { - dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " - "ack_ackno=%llu, ACKED!\n", - dccp_role(sk), avr->avr_ack_runlen, - (unsigned long long)avr->avr_ack_seqno, - (unsigned long long)avr->avr_ack_ackno); - dccp_ackvec_throw_record(av, avr); - break; - } else if (avr->avr_ack_seqno > ackno) - break; /* old news */ - } -} - -static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, - struct sock *sk, u64 *ackno, - const unsigned char len, - const unsigned char *vector) -{ - unsigned char i; - struct dccp_ackvec_record *avr; - - /* Check if we actually sent an ACK vector */ - if (list_empty(&av->av_records)) - return; - - i = len; - /* - * XXX - * I think it might be more efficient to work backwards. See comment on - * rcv_ackno. -sorbo. - */ - avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); - while (i--) { - const u8 rl = dccp_ackvec_runlen(vector); - u64 ackno_end_rl; - - dccp_set_seqno(&ackno_end_rl, *ackno - rl); - - /* - * If our AVR sequence number is greater than the ack, go - * forward in the AVR list until it is not so. - */ - list_for_each_entry_from(avr, &av->av_records, avr_node) { - if (!after48(avr->avr_ack_seqno, *ackno)) - goto found; - } - /* End of the av_records list, not found, exit */ - break; -found: - if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { - if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) { - dccp_pr_debug("%s ACK vector 0, len=%d, " - "ack_seqno=%llu, ack_ackno=%llu, " - "ACKED!\n", - dccp_role(sk), len, - (unsigned long long) - avr->avr_ack_seqno, - (unsigned long long) - avr->avr_ack_ackno); - dccp_ackvec_throw_record(av, avr); - break; - } - /* - * If it wasn't received, continue scanning... we might - * find another one. - */ - } - - dccp_set_seqno(ackno, ackno_end_rl - 1); - ++vector; - } -} - -int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, - u64 *ackno, const u8 opt, const u8 *value, const u8 len) -{ - if (len > DCCP_SINGLE_OPT_MAXLEN) - return -1; - - /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */ - dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk, - ackno, len, value); - return 0; -} - /** * dccp_ackvec_clear_state - Perform house-keeping / garbage-collection * This routine is called when the peer acknowledges the receipt of Ack Vectors --- a/net/dccp/Kconfig +++ b/net/dccp/Kconfig @@ -25,9 +25,6 @@ config INET_DCCP_DIAG def_tristate y if (IP_DCCP = y && INET_DIAG = y) def_tristate m -config IP_DCCP_ACKVEC - bool - source "net/dccp/ccids/Kconfig" menu "DCCP Kernel Hacking" --- a/net/dccp/ccids/Kconfig +++ b/net/dccp/ccids/Kconfig @@ -4,7 +4,6 @@ menu "DCCP CCIDs Configuration (EXPERIMENTAL)" config IP_DCCP_CCID2 tristate "CCID2 (TCP-Like) (EXPERIMENTAL)" def_tristate IP_DCCP - select IP_DCCP_ACKVEC ---help--- CCID 2, TCP-like Congestion Control, denotes Additive Increase, Multiplicative Decrease (AIMD) congestion control with behavior --- a/net/dccp/Makefile +++ b/net/dccp/Makefile @@ -1,6 +1,7 @@ obj-$(CONFIG_IP_DCCP) += dccp.o dccp_ipv4.o -dccp-y := ccid.o feat.o input.o minisocks.o options.o output.o proto.o timer.o +dccp-y := ccid.o feat.o input.o minisocks.o options.o \ + output.o proto.o timer.o ackvec.o dccp_ipv4-y := ipv4.o @@ -8,8 +9,6 @@ dccp_ipv4-y := ipv4.o obj-$(subst y,$(CONFIG_IP_DCCP),$(CONFIG_IPV6)) += dccp_ipv6.o dccp_ipv6-y := ipv6.o -dccp-$(CONFIG_IP_DCCP_ACKVEC) += ackvec.o - obj-$(CONFIG_INET_DCCP_DIAG) += dccp_diag.o obj-$(CONFIG_NET_DCCPPROBE) += dccp_probe.o --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -62,7 +62,6 @@ static inline u8 dccp_ackvec_state(const u8 *cell) * %DCCP_SINGLE_OPT_MAXLEN cells in the live portion of @av_buf * @av_overflow: if 1 then buf_head == buf_tail indicates buffer wraparound * @av_records: list of %dccp_ackvec_record (Ack Vectors sent previously) - * @av_veclen: length of the live portion of @av_buf */ struct dccp_ackvec { u8 av_buf[DCCPAV_MAX_ACKVEC_LEN]; @@ -73,7 +72,6 @@ struct dccp_ackvec { bool av_buf_nonce[DCCPAV_NUM_ACKVECS]; u8 av_overflow:1; struct list_head av_records; - u16 av_vec_len; }; /** struct dccp_ackvec_record - Records information about sent Ack Vectors @@ -99,25 +97,12 @@ struct dccp_ackvec_record { u8 avr_ack_nonce:1; }; -struct sock; -struct sk_buff; - -#ifdef CONFIG_IP_DCCP_ACKVEC -extern int dccp_ackvec_init(void); +extern int dccp_ackvec_init(void); extern void dccp_ackvec_exit(void); extern struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority); extern void dccp_ackvec_free(struct dccp_ackvec *av); -extern int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, - const u64 ackno, const u8 state); - -extern void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, - struct sock *sk, const u64 ackno); -extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, - u64 *ackno, const u8 opt, - const u8 *value, const u8 len); - extern void dccp_ackvec_input(struct dccp_ackvec *av, u64 seqno, u8 state); extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); extern void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno); @@ -127,66 +112,4 @@ static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) { return av->av_overflow == 0 && av->av_buf_head == av->av_buf_tail; } -#else /* CONFIG_IP_DCCP_ACKVEC */ -static inline int dccp_ackvec_init(void) -{ - return 0; -} - -static inline void dccp_ackvec_exit(void) -{ -} - -static inline struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) -{ - return NULL; -} - -static inline void dccp_ackvec_free(struct dccp_ackvec *av) -{ -} - -static inline void dccp_ackvec_input(struct dccp_ackvec *av, u64 seq, u8 state) -{ - -} - -static inline int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, - const u64 ackno, const u8 state) -{ - return -1; -} - -static inline void dccp_ackvec_clear_state(struct dccp_ackvec *av, - const u64 ackno) -{ -} - -static inline void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, - struct sock *sk, const u64 ackno) -{ -} - -static inline int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, - const u64 *ackno, const u8 opt, - const u8 *value, const u8 len) -{ - return -1; -} - -static inline int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 nonce) -{ - return -1; -} - -static inline u16 dccp_ackvec_buflen(const struct dccp_ackvec *av) -{ - return 0; -} - -static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) -{ - return true; -} -#endif /* CONFIG_IP_DCCP_ACKVEC */ #endif /* _ACKVEC_H */ ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 10/10] [ACKVEC]: Separate option parsing from CCID processing 2008-02-21 9:09 ` [PATCH 09/10] [ACKVEC]: Remove old infrastructure Gerrit Renker @ 2008-02-21 9:09 ` Gerrit Renker 0 siblings, 0 replies; 11+ messages in thread From: Gerrit Renker @ 2008-02-21 9:09 UTC (permalink / raw) To: acme; +Cc: dccp, netdev, Gerrit Renker 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> --- net/dccp/ackvec.c | 28 ++++++++++ net/dccp/ackvec.h | 19 +++++++ net/dccp/ccids/ccid2.c | 136 +++++++++++++++--------------------------------- net/dccp/ccids/ccid2.h | 2 + net/dccp/options.c | 17 ++++--- 5 files changed, 102 insertions(+), 100 deletions(-) --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -112,4 +112,23 @@ static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) { return av->av_overflow == 0 && av->av_buf_head == av->av_buf_tail; } + +/** + * struct dccp_ackvec_parsed - Record offsets of Ack Vectors in skb + * @vec: start of vector (offset into skb) + * @len: length of @vec + * @nonce: whether @vec had an ECN nonce of 0 or 1 + * @node: FIFO - arranged in descending order of ack_ackno + * This structure is used by CCIDs to access Ack Vectors in a received skb. + */ +struct dccp_ackvec_parsed { + u8 *vec, + len, + nonce:1; + struct list_head node; +}; + +extern int dccp_ackvec_parsed_add(struct list_head *head, + u8 *vec, u8 len, u8 nonce); +extern void dccp_ackvec_parsed_cleanup(struct list_head *parsed_chunks); #endif /* _ACKVEC_H */ --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -345,6 +345,34 @@ free_records: } } +/* + * Routines to keep track of Ack Vectors received in an skb + */ +int dccp_ackvec_parsed_add(struct list_head *head, u8 *vec, u8 len, u8 nonce) +{ + struct dccp_ackvec_parsed *new = kmalloc(sizeof(*new), GFP_ATOMIC); + + if (new == NULL) + return -ENOBUFS; + new->vec = vec; + new->len = len; + new->nonce = nonce; + + list_add_tail(&new->node, head); + return 0; +} +EXPORT_SYMBOL_GPL(dccp_ackvec_parsed_add); + +void dccp_ackvec_parsed_cleanup(struct list_head *parsed_chunks) +{ + struct dccp_ackvec_parsed *cur, *next; + + list_for_each_entry_safe(cur, next, parsed_chunks, node) + kfree(cur); + INIT_LIST_HEAD(parsed_chunks); +} +EXPORT_SYMBOL_GPL(dccp_ackvec_parsed_cleanup); + int __init dccp_ackvec_init(void) { dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -135,13 +135,6 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, if (rc) goto out_invalid_option; break; - case DCCPO_ACK_VECTOR_0: - case DCCPO_ACK_VECTOR_1: - if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */ - break; - dccp_pr_debug("%s Ack Vector (len=%u)\n", dccp_role(sk), - len); - break; case DCCPO_TIMESTAMP: if (len != 4) goto out_invalid_option; @@ -229,6 +222,16 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, value) != 0) goto out_invalid_option; break; + case DCCPO_ACK_VECTOR_0: + case DCCPO_ACK_VECTOR_1: + if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */ + break; + /* + * Ack vectors are processed by the TX CCID if it is + * interested. The RX CCID need not parse Ack Vectors, + * since it is only interested in clearing old state. + * Fall through. + */ case DCCPO_MIN_TX_CCID_SPECIFIC ... DCCPO_MAX_TX_CCID_SPECIFIC: if (ccid_hc_tx_parse_options(dp->dccps_hc_tx_ccid, sk, opt, len, value - options, --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -47,6 +47,7 @@ struct ccid2_seq { * @ccid2hctx_lastrtt -time RTT was last measured * @ccid2hctx_rpseq - last consecutive seqno * @ccid2hctx_rpdupack - dupacks since rpseq + * @ccid2hctx_av_chunks: list of Ack Vectors received on current skb */ struct ccid2_hc_tx_sock { u32 ccid2hctx_cwnd; @@ -66,6 +67,7 @@ struct ccid2_hc_tx_sock { int ccid2hctx_rpdupack; unsigned long ccid2hctx_last_cong; u64 ccid2hctx_high_ack; + struct list_head ccid2hctx_av_chunks; }; struct ccid2_hc_rx_sock { --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -320,68 +320,6 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) #endif } -/* XXX Lame code duplication! - * returns -1 if none was found. - * else returns the next offset to use in the function call. - */ -static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset, - unsigned char **vec, unsigned char *veclen) -{ - const struct dccp_hdr *dh = dccp_hdr(skb); - unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb); - unsigned char *opt_ptr; - const unsigned char *opt_end = (unsigned char *)dh + - (dh->dccph_doff * 4); - unsigned char opt, len; - unsigned char *value; - - BUG_ON(offset < 0); - options += offset; - opt_ptr = options; - if (opt_ptr >= opt_end) - return -1; - - while (opt_ptr != opt_end) { - opt = *opt_ptr++; - len = 0; - value = NULL; - - /* Check if this isn't a single byte option */ - if (opt > DCCPO_MAX_RESERVED) { - if (opt_ptr == opt_end) - goto out_invalid_option; - - len = *opt_ptr++; - if (len < 3) - goto out_invalid_option; - /* - * Remove the type and len fields, leaving - * just the value size - */ - len -= 2; - value = opt_ptr; - opt_ptr += len; - - if (opt_ptr > opt_end) - goto out_invalid_option; - } - - switch (opt) { - case DCCPO_ACK_VECTOR_0: - case DCCPO_ACK_VECTOR_1: - *vec = value; - *veclen = len; - return offset + (opt_ptr - options); - } - } - - return -1; - -out_invalid_option: - DCCP_BUG("Invalid option - this should not happen (previous parsing)!"); - return -1; -} - static void ccid2_hc_tx_kill_rto_timer(struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); @@ -502,15 +440,28 @@ static void ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp) ccid2_change_l_ack_ratio(sk, hctx->ccid2hctx_cwnd); } +static int ccid2_hc_tx_parse_options(struct sock *sk, unsigned char option, + unsigned char len, u16 idx, + unsigned char *value) +{ + struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + + switch (option) { + case DCCPO_ACK_VECTOR_0: + case DCCPO_ACK_VECTOR_1: + return dccp_ackvec_parsed_add(&hctx->ccid2hctx_av_chunks, value, + len, option - DCCPO_ACK_VECTOR_0); + } + return 0; +} + static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct dccp_ackvec_parsed *avp; u64 ackno, seqno; struct ccid2_seq *seqp; - unsigned char *vector; - unsigned char veclen; - int offset = 0; int done = 0; unsigned int maxincr = 0; @@ -545,17 +496,12 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) } /* check forward path congestion */ - /* still didn't send out new data packets */ - if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) + if (dccp_packet_without_ack(skb)) return; - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case DCCP_PKT_ACK: - case DCCP_PKT_DATAACK: - break; - default: - return; - } + /* still didn't send out new data packets */ + if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) + goto done; ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq; if (after48(ackno, hctx->ccid2hctx_high_ack)) @@ -579,15 +525,16 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2); /* go through all ack vectors */ - while ((offset = ccid2_ackvector(sk, skb, offset, - &vector, &veclen)) != -1) { + list_for_each_entry(avp, &hctx->ccid2hctx_av_chunks, node) { /* go through this ack vector */ - while (veclen--) { - u64 ackno_end_rl = SUB48(ackno, dccp_ackvec_runlen(vector)); + for (; avp->len--; avp->vec++) { + u64 ackno_end_rl = SUB48(ackno, + dccp_ackvec_runlen(avp->vec)); - ccid2_pr_debug("ackvec start:%llu end:%llu\n", + ccid2_pr_debug("ackvec %llu |%u,%u|\n", (unsigned long long)ackno, - (unsigned long long)ackno_end_rl); + dccp_ackvec_state(avp->vec) >> 6, + dccp_ackvec_runlen(avp->vec)); /* if the seqno we are analyzing is larger than the * current ackno, then move towards the tail of our * seqnos. @@ -606,7 +553,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) * run length */ while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) { - const u8 state = dccp_ackvec_state(vector); + const u8 state = dccp_ackvec_state(avp->vec); /* new packet received or marked */ if (state != DCCPAV_NOT_RECEIVED && @@ -633,7 +580,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) break; ackno = SUB48(ackno_end_rl, 1); - vector++; } if (done) break; @@ -697,6 +643,8 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) } ccid2_hc_tx_check_sanity(hctx); +done: + dccp_ackvec_parsed_cleanup(&hctx->ccid2hctx_av_chunks); } static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) @@ -731,6 +679,7 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) hctx->ccid2hctx_last_cong = jiffies; setup_timer(&hctx->ccid2hctx_rtotimer, ccid2_hc_tx_rto_expire, (unsigned long)sk); + INIT_LIST_HEAD(&hctx->ccid2hctx_av_chunks); ccid2_hc_tx_check_sanity(hctx); return 0; @@ -766,17 +715,18 @@ static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) } static struct ccid_operations ccid2 = { - .ccid_id = DCCPC_CCID2, - .ccid_name = "TCP-like", - .ccid_owner = THIS_MODULE, - .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), - .ccid_hc_tx_init = ccid2_hc_tx_init, - .ccid_hc_tx_exit = ccid2_hc_tx_exit, - .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet, - .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent, - .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv, - .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock), - .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv, + .ccid_id = DCCPC_CCID2, + .ccid_name = "TCP-like", + .ccid_owner = THIS_MODULE, + .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), + .ccid_hc_tx_init = ccid2_hc_tx_init, + .ccid_hc_tx_exit = ccid2_hc_tx_exit, + .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet, + .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent, + .ccid_hc_tx_parse_options = ccid2_hc_tx_parse_options, + .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv, + .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock), + .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv, }; #ifdef CONFIG_IP_DCCP_CCID2_DEBUG ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2008-02-21 9:12 UTC | newest] Thread overview: 11+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2008-02-21 9:09 [DCCP] [Patch 0/10]: Finish and repair existing Ack Vector implementation Gerrit Renker 2008-02-21 9:09 ` [PATCH 01/10] [ACKVEC]: Need to ignore Ack Vectors on request sockets Gerrit Renker 2008-02-21 9:09 ` [PATCH 02/10] [ACKVEC]: Ack Vector interface clean-up Gerrit Renker 2008-02-21 9:09 ` [PATCH 03/10] [ACKVEC]: Separate internals of Ack Vectors from option-parsing code Gerrit Renker 2008-02-21 9:09 ` [PATCH 04/10] [ACKVEC]: Implementation of circular Ack Vector buffer with overflow handling Gerrit Renker 2008-02-21 9:09 ` [PATCH 05/10] [ACKVEC]: Algorithm to update buffer state Gerrit Renker 2008-02-21 9:09 ` [PATCH 06/10] [ACKVEC]: Update code for the Ack Vector input/registration routine Gerrit Renker 2008-02-21 9:09 ` [PATCH 07/10] [ACKVEC]: Consolidate Ack-Vector processing within main DCCP module Gerrit Renker 2008-02-21 9:09 ` [PATCH 08/10] [ACKVEC]: Schedule SyncAck when running out of space Gerrit Renker 2008-02-21 9:09 ` [PATCH 09/10] [ACKVEC]: Remove old infrastructure Gerrit Renker 2008-02-21 9:09 ` [PATCH 10/10] [ACKVEC]: Separate option parsing from CCID processing Gerrit Renker
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox