[PATCH 6/43]: New infrastructure for loss detection

[PATCH 6/43]: New infrastructure for loss detection

[Gerrit Renker]

[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@erg.abdn.ac.uk>
---
 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,

Re: [PATCH 6/43]: New infrastructure for loss detection

[Eddie Kohler]

Hi Gerrit,

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.

Eddie


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@erg.abdn.ac.uk>
> ---
>  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@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 6/43]: New infrastructure for loss detection

[Gerrit Renker]

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@erg.abdn.ac.uk>
|  > ---
|  >  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@vger.kernel.org
|  > 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@vger.kernel.org
|  More majordomo info at  http://vger.kernel.org/majordomo-info.html
|  
|