Eddie - | Sorry if this is a stupid question, but are the entries corresponding to Loss | Intervals stored elsewhere? You need at least 8 entries for that mandatory | option. 10 patches too early - this patch does only the receiver history structure. The Loss Intervals database structure starts at patch #16 (12a) and ends at patch #24. The number of entries is 9, 8 loss intervals plus space for tracking I_0. | | | Gerrit Renker wrote: | > [CCID 3]: New infrastructure for loss detection | > | > This provides a generic RX history unit for TFRC based protocols. | > | > Why? | > I have spent several weeks trying to make sense out of the existing, circular-list | > based RX history implementation. It is complex, heavy-weight and puts nothing but | > stones in the way of fixing the identified current bugs in loss detection. | > | > A full list implementation is in fact not needed: both for RTT estimation | > (needed only to compute the first loss interval, RFC 3448, 6.3.1) and for | > loss detection, only a minimum of 4 entries is needed. The overhead of | > allocating and later garbage-collecting further entries is not justified, | > and it introduces a memory and processing bottleneck. | > | > The present design is lightweight and object-oriented: | > * only the minimum number of entries is used; | > * circular array of pointers: | > - faster swapping of entries for sorting, | > - the indexed-array semantics matches the requirments of loss detection | > (3 consecutive packets) and RTT estimation (also consecutive packets) | > much more naturally than a doubly-linked list; | > * one and the same structure is used both for RTT sampling and for | > loss detection, reducing memory demands; | > * generic definition, can later be reused for small-packet variant of | > CCID 3 etc. | > | > This patch lays the foundation in terms of the main data structure with some rudimentary | > routines for basic access. Further patches will fill in the details with regard to CCID3. | > | > Details of the algorithm are documented and illustrated in section 3 of | > http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/ | > | > Signed-off-by: Gerrit Renker <gerrit@xxxxxxxxxxxxxx> | > --- | > net/dccp/ccids/lib/packet_history.h | 101 ++++++++++++++++++++++++++++++++++++ | > 1 file changed, 101 insertions(+) | > | > --- a/net/dccp/ccids/lib/packet_history.h | > +++ b/net/dccp/ccids/lib/packet_history.h | > @@ -45,6 +45,9 @@ | > /* Number of later packets received before one is considered lost */ | > #define TFRC_RECV_NUM_LATE_LOSS 3 | > | > +/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */ | > +#define NDUPACK 3 | > + | > #define TFRC_WIN_COUNT_PER_RTT 4 | > /* Subtraction a-b modulo-16, respects circular wrap-around */ | > #define SUB16(a,b) (((a) + 16 - (b)) & 0xF) | > @@ -106,6 +109,104 @@ struct dccp_rx_hist { | > extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name); | > extern void dccp_rx_hist_delete(struct dccp_rx_hist *hist); | > | > +/** | > + * tfrc_rx_hist - RX history structure for TFRC-based protocols | > + * | > + * @ring: Packet history for RTT sampling and loss detection | > + * @loss_count: Number of entries in circular history | > + * @loss_start: Movable index (for loss detection) | > + * @rtt_sample_prev: Used during RTT sampling, points to candidate entry | > + * @lock: Serialize concurrent access | > + */ | > +struct tfrc_rx_hist { | > + struct dccp_rx_hist_entry *ring[NDUPACK + 1]; | > + u8 loss_count:2, | > + loss_start:2; | > +#define rtt_sample_prev loss_start | > + spinlock_t lock; | > +}; | > + | > +/* | > + * Macros for loss detection. | > + * @loss_prev: entry with highest-received-seqno before loss was detected | > + * @hist_index: index to reach n-th entry after loss_start | > + * @hist_entry: return the n-th history entry after loss_start | > + * @last_rcv: entry with highest-received-seqno so far | > + */ | > +#define loss_prev(h) (h)->ring[(h)->loss_start] | > +#define hist_index(h, n) (((h)->loss_start + (n)) & NDUPACK) | > +#define hist_entry(h, n) (h)->ring[hist_index(h, n)] | > +#define last_rcv(h) (h)->ring[hist_index(h, (h)->loss_count)] | > + | > +/* | > + * Macros to access history entries for RTT sampling. | > + * @rtt_last_s: reference entry to compute RTT samples against | > + * @rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry | > + */ | > +#define rtt_last_s(h) (h)->ring[0] | > +#define rtt_prev_s(h) (h)->ring[(h)->rtt_sample_prev] | > + | > +/* initialise loss detection and disable RTT sampling */ | > +static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h) | > +{ | > + h->loss_count = 1; | > +} | > + | > +/* indicate whether previously a packet was detected missing */ | > +static inline int tfrc_rx_loss_pending(struct tfrc_rx_hist *h) | > +{ | > + return h->loss_count; | > +} | > + | > +/* any data packets missing between last reception and skb ? */ | > +static inline int tfrc_rx_new_loss_indicated(struct tfrc_rx_hist *h, | > + struct sk_buff *skb, u32 ndp) | > +{ | > + int delta = dccp_delta_seqno(last_rcv(h)->dccphrx_seqno, | > + DCCP_SKB_CB(skb)->dccpd_seq); | > + | > + if (delta > 1 && ndp < delta) | > + tfrc_rx_hist_loss_indicated(h); | > + | > + return tfrc_rx_loss_pending(h); | > +} | > + | > +/* has the packet contained in skb been seen before ? */ | > +static inline int tfrc_rx_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) | > +{ | > + const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; | > + int i; | > + | > + if (dccp_delta_seqno(loss_prev(h)->dccphrx_seqno, seq) <= 0) | > + return 1; | > + | > + for (i = 1; i <= h->loss_count; i++) | > + if (dccp_delta_seqno(hist_entry(h, i)->dccphrx_seqno, seq) == 0) | > + return 1; | > + | > + return 0; | > +} | > + | > +/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */ | > +static inline s64 tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist *h, u8 e1, u8 e2) | > +{ | > + DCCP_BUG_ON(e1 > h->loss_count || e2 > h->loss_count); | > + | > + return dccp_delta_seqno(hist_entry(h, e1)->dccphrx_seqno, | > + hist_entry(h, e2)->dccphrx_seqno); | > +} | > + | > +static inline void tfrc_rx_hist_swap(struct dccp_rx_hist_entry **a, | > + struct dccp_rx_hist_entry **b) | > +{ | > + struct dccp_rx_hist_entry *tmp = *a; | > + | > + *a = *b; | > + *b = tmp; | > +} | > + | > + | > +/* Older history management functions */ | > static inline struct dccp_rx_hist_entry * | > dccp_rx_hist_entry_new(struct dccp_rx_hist *hist, | > const struct sock *sk, | > - | > To unsubscribe from this list: send the line "unsubscribe dccp" in | > the body of a message to majordomo@xxxxxxxxxxxxxxx | > More majordomo info at http://vger.kernel.org/majordomo-info.html | - | To unsubscribe from this list: send the line "unsubscribe dccp" in | the body of a message to majordomo@xxxxxxxxxxxxxxx | More majordomo info at http://vger.kernel.org/majordomo-info.html | | - To unsubscribe from this list: send the line "unsubscribe dccp" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
