: Bug fix and a new sending-policy interface

PATCH In review Gerrit Renker 2 participants 4 messages May 12, 2008 1 message not in the archive

Subsystems (3)

Networking Network drivers Documentation

lore

Share & tools

lore

A message that is not in the archive (sent off-list or not yet received): bug_fix_and_qpolicy_interface

Gerrit Renker

author

2008-05-12 07:48 UTC #1 lore raw

cover : Bug fix and a new sending-policy interface

One bug fix and a new packet dequeuing interface for DCCP developed by Tomasz Grobelny, which has been discussed on dccp@vger.

Patch #1: Bug fix for CCID-3 (ported to CCID-4, too), where a too high t_delta
(RFC 3448, 4.6) was used. Analysis shows that the t_delta socket field is not meaningful, it is replaced by an appropriate constant.

Patch #2: Provides a new basis/interface for sending packets, allowing the
user to set different send policies. This is especially interesting for multimedia applications which have to interact with the congestion control part of DCCP, where packets may be have different priorities (I/P/B video frames, re-synch frames) and may be subject to a playout.

Test tree disclaimer:
==========All patches are eventually meant for mainline but are kept in the DCCP test tree for testing and possible improvement. Comments and in particular testing are therefore especially welcome.

The DCCP test tree contains the most recent bug fixes and code updates. The attribute `test' does not indicate minor quality - all patches have been checked, the entire tree is fully bisectable and has been compile-tested on several different platforms.

It can be checked out from

	git://eden-feed.erg.abdn.ac.uk/dccp_exp
	-> subtree `dccp' for DCCP test tree
	-> subtree `ccid4' for CCID-4 subtree

Further information is on
http://www.linux-foundation.org/en/Net:DCCP_Testing#Experimental_DCCP_source_tree

The University of Aberdeen is a charity registered in Scotland, No SC013683.

Gerrit Renker

author

2008-05-12 07:48 UTC #2 lore raw

PATCH 1/2 : Bug fix for the inter-packet scheduling algorithm

This fixes a subtle bug in the calculation of the inter-packet gap and shows that t_delta, as it is currently used, is not needed. And hence replaced.

The algorithm from RFC 3448, 4.6 below continually computes a send time t_nom, which is initialised with the current time t_now; t_gran = 1E6 / HZ specifies the scheduling granularity, s the packet size, and X the sending rate:

t_distance = t_nom - t_now; // in microseconds
t_delta = min(t_ipi, t_gran) / 2; // `delta' parameter in microseconds

  if (t_distance >= t_delta) {
	reschedule after (t_distance / 1000) milliseconds;
  } else {
  	t_ipi  = s / X;			// inter-packet interval in usec
	t_nom += t_ipi;			// compute the next send time
	send packet now;

}

1) Description of the bug
-------------------------
Rescheduling requires a conversion into milliseconds, due to this call chain:

* ccid3_hc_tx_send_packet() returns a timeout in milliseconds,
* this value is converted by msecs_to_jiffies() in dccp_write_xmit(),
* and finally used as jiffy-expires-value for sk_reset_timer().

The highest jiffy resolution with HZ00 is 1 millisecond, so using a higher granularity does not seem to make much sense here.

As a consequence, values of t_distance < 1000 are truncated to 0. This issue has so far been resolved by using instead

if (t_distance >= t_delta + 1000)

	reschedule after (t_distance / 1000) milliseconds;

The bug is in artificially inflating t_delta to t_delta' = t_delta + 1000. This is unnecessarily large, a more adequate value is t_delta' = max(t_delta, 1000).

2) Consequences of using the corrected t_delta'
-----------------------------------------------
Since t_delta <= t_gran/2 = 10^6/(2*HZ), we have t_delta <= 1000 as long as HZ >= 500. This means that t_delta' = max(1000, t_delta) is constant at 1000.

On the other hand, when using a coarse HZ value of HZ < 500, we have three sub-cases that can all be reduced to using another constant of t_gran/2.

(a) The first case arises when t_ipi > t_gran. Here t_delta' is the constant

     t_delta' = max(1000, t_gran/2) = t_gran/2.

(b) If t_ipi <= 2000 < t_gran = 10^6/HZ usec, then t_delta = t_ipi/2 <= 1000,

     so that t_delta' = max(1000, t_delta) = 1000 < t_gran/2.

In the second and third cases we have delay values less than t_gran/2, which is in the order of less than or equal to half a jiffy.

How these are treated depends on how fractions of a jiffy are handled: they are either always rounded down to 0, or always rounded up to 1 jiffy (assuming non-zero values). In both cases the error is on average in the order of 50%.

Thus we are not increasing the error when in the second/third case we replace a value less than t_gran/2 with 0, by setting t_delta' to the constant t_gran/2.

3) Summary
----------
Fixing (1) and considering (2), the patch replaces t_delta with a constant, whose value depends on CONFIG_HZ, changing the above algorithm to:

if (t_distance >= t_delta')

	reschedule after (t_distance / 1000) milliseconds;

where t_delta' = 10^6/(2*HZ) if HZ < 500, and t_delta' = 1000 otherwise.

Signed-off-by Gerrit Renker <[email protected]>

---
 net/dccp/ccids/ccid3.h |   19 ++++++++++++++-----
 net/dccp/ccids/ccid3.c |   17 +++++++----------
 2 files changed, 21 insertions(+), 15 deletions(-)

net/dccp/ccids/ccid3.h +14 -5

@@ -47,12 +47,23 @@
 /* Two seconds as per RFC 3448 4.2 */
 #define TFRC_INITIAL_TIMEOUT	   (2 * USEC_PER_SEC)
 
-/* In usecs - half the scheduling granularity as per RFC3448 4.6 */
-#define TFRC_OPSYS_HALF_TIME_GRAN  (USEC_PER_SEC / (2 * HZ))
-
 /* Parameter t_mbi from [RFC 3448, 4.3]: backoff interval in seconds */
 #define TFRC_T_MBI		   64
 
+/*
+ * The t_delta parameter (RFC 3448, 4.6): delays of less than %USEC_PER_MSEC are
+ * rounded down to 0, since sk_reset_timer() here uses millisecond granularity.
+ * Hence we can use a constant t_delta = %USEC_PER_MSEC when HZ >= 500. A coarse
+ * resolution of HZ < 500 means that the error is below one timer tick (t_gran)
+ * when using the constant t_delta  =  t_gran / 2  =  %USEC_PER_SEC / (2 * HZ).
+ */
+#if (HZ >= 500)
+# define TFRC_T_DELTA		   USEC_PER_MSEC
+#else
+# define TFRC_T_DELTA		   USEC_PER_SEC / (2 * HZ)
+# warning Coarse CONFIG_HZ resolution -- higher value recommended for CCID-3.
+#endif
+
 enum ccid3_options {
 	TFRC_OPT_LOSS_EVENT_RATE = 192,
 	TFRC_OPT_LOSS_INTERVALS	 = 193,

@@ -83,7 +94,6 @@ enum ccid3_hc_tx_states {
  * @no_feedback_timer - Handle to no feedback timer
  * @t_ld - Time last doubled during slow start
  * @t_nom - Nominal send time of next packet
- * @delta - Send timer delta (RFC 3448, 4.6) in usecs
  * @hist - Packet history
  */
 struct ccid3_hc_tx_sock {

@@ -101,7 +111,6 @@ struct ccid3_hc_tx_sock {
 	struct timer_list		no_feedback_timer;
 	ktime_t				t_ld;
 	ktime_t				t_nom;
-	u32				delta;
 	struct tfrc_tx_hist_entry	*hist;
 };

net/dccp/ccids/ccid3.c +7 ~~-10~~

@@ -90,19 +90,16 @@ static inline u64 rfc3390_initial_rate(struct sock *sk)
 	return scaled_div(w_init << 6, hctx->rtt);
 }
 
-/*
- * Recalculate t_ipi and delta (should be called whenever X changes)
+/**
+ * ccid3_update_send_interval  -  Calculate new t_ipi = s / X_inst
+ * This respects the granularity of X_inst (64 * bytes/second).
  */
 static void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx)
 {
-	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
 	hctx->t_ipi = scaled_div32(((u64)hctx->s) << 6, hctx->x);
 
-	/* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
-	hctx->delta = min_t(u32, hctx->t_ipi / 2, TFRC_OPSYS_HALF_TIME_GRAN);
-
-	ccid3_pr_debug("t_ipi=%u, delta=%u, s=%u, X=%u\n", hctx->t_ipi,
-		       hctx->delta, hctx->s, (unsigned)(hctx->x >> 6));
+	ccid3_pr_debug("t_ipi=%u, s=%u, X=%u\n", hctx->t_ipi,
+		       hctx->s, (unsigned)(hctx->x >> 6));
 }
 
 static u32 ccid3_hc_tx_idle_rtt(struct ccid3_hc_tx_sock *hctx, ktime_t now)

@@ -336,8 +333,8 @@ static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb)
 		 * else
 		 *       // send the packet in (t_nom - t_now) milliseconds.
 		 */
-		if (delay - (s64)hctx->delta >= 1000)
-			return (u32)delay / 1000L;
+		if (delay >= TFRC_T_DELTA)
+			return (u32)delay / USEC_PER_MSEC;
 
 		ccid3_hc_tx_update_win_count(hctx, now);
 	}

The University of Aberdeen is a charity registered in Scotland, No SC013683.

Gerrit Renker

author

2008-05-12 07:48 UTC #3 lore raw

PATCH 2/2 : Policy-based packet dequeueing

From: Tomasz Grobelny <[email protected]>

This patch adds a generic infrastructure for policy-based dequeueing of TX packets and provides two policies:
* a simple FIFO policy (which is the default) and
* a priority based policy (set via socket options).
Both policies honour the tx_qlen sysctl for the maximum size of the write queue (can be overridden via socket options).

The priority policy uses skb->priority internally to assign an u32 priority identifier, using the same ranking as SO_PRIORITY. The skb->priority field is set to 0 when the packet leaves DCCP. The priority is supplied as ancillary data using cmsg(3), the patch also provides the requisite parsing routines.

Signed-off-by Gerrit Renker <[email protected]>

---
 Documentation/networking/dccp.txt |   19 +++++
 include/linux/dccp.h              |   19 +++++
 net/dccp/Makefile                 |    2 
 net/dccp/dccp.h                   |   12 +++
 net/dccp/output.c                 |    7 --
 net/dccp/proto.c                  |   67 +++++++++++++++++++-
 net/dccp/qpolicy.c                |  126 ++++++++++++++++++++++++++++++++++++++
 7 files changed, 244 insertions(+), 8 deletions(-)

Documentation/networking/dccp.txt +19 -0

@@ -45,6 +45,25 @@ http://linux-net.osdl.org/index.php/DCCP
 
 Socket options
 =======
+DCCP_SOCKOPT_QPOLICY_ID sets the dequeuing policy for outgoing packets. It takes
+a policy ID as argument and can only be set before the connection (i.e. changes
+during an established connection are not supported). Currently, two policies are
+defined: the "simple" policy (DCCPQ_POLICY_SIMPLE), which does nothing special,
+and a priority-based variant (DCCPQ_POLICY_PRIO). The latter allows to pass an
+u32 priority value as ancillary data to sendmsg(), where higher numbers indicate
+a higher packet priority (similar to SO_PRIORITY). This ancillary data needs to
+be formatted using a cmsg(3) message header filled in as follows:
+	cmsg->cmsg_level = SOL_DCCP;
+	cmsg->cmsg_type	 = DCCP_SCM_PRIORITY;
+	cmsg->cmsg_len	 = CMSG_LEN(sizeof(uint32_t));	/* or CMSG_LEN(4) */
+
+DCCP_SOCKOPT_QPOLICY_TXQLEN sets the maximum length of the output queue. A zero
+value is always interpreted as unbounded queue length. If different from zero,
+the interpretation of this parameter depends on the current dequeuing policy
+(see above): the "simple" policy will enforce a fixed queue size by returning
+EAGAIN, whereas the "prio" policy enforces a fixed queue length by dropping the
+lowest-priority packet first. The default value for this parameter is
+initialised from /proc/sys/net/dccp/default/tx_qlen.
 
 DCCP_SOCKOPT_SERVICE sets the service. The specification mandates use of
 service codes (RFC 4340, sec. 8.1.2); if this socket option is not set,

net/dccp/dccp.h +12 -0

@@ -215,6 +215,18 @@ extern void dccp_reqsk_send_ack(struct s
 extern void dccp_send_sync(struct sock *sk, const u64 seq,
 			   const enum dccp_pkt_type pkt_type);
 
+/*
+ * TX Packet Dequeueing Interface
+ */
+extern void		dccp_qpolicy_push(struct sock *sk, struct sk_buff *skb);
+extern bool		dccp_qpolicy_full(struct sock *sk);
+extern void		dccp_qpolicy_drop(struct sock *sk, struct sk_buff *skb);
+extern struct sk_buff	*dccp_qpolicy_top(struct sock *sk);
+extern struct sk_buff	*dccp_qpolicy_pop(struct sock *sk);
+
+/*
+ * TX Packet Output and TX Timers
+ */
 extern void dccp_write_xmit(struct sock *sk);
 extern void dccp_write_space(struct sock *sk);
 extern void dccp_flush_write_queue(struct sock *sk, long *time_budget);

net/dccp/Makefile +1 -1

@@ -1,7 +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 ackvec.o
+	  qpolicy.o output.o proto.o timer.o ackvec.o
 
 dccp_ipv4-y := ipv4.o

net/dccp/qpolicy.c new file +126 -0

126 lines not on this page · raw message

net/dccp/output.c +3 -4

@@ -238,7 +238,7 @@ static void dccp_xmit_packet(struct sock
 {
 	int err, len;
 	struct dccp_sock *dp = dccp_sk(sk);
-	struct sk_buff *skb = skb_dequeue(&sk->sk_write_queue);
+	struct sk_buff *skb = dccp_qpolicy_pop(sk);
 
 	if (unlikely(skb = NULL))
 		return;

@@ -328,7 +328,7 @@ void dccp_write_xmit(struct sock *sk)
 	struct dccp_sock *dp = dccp_sk(sk);
 	struct sk_buff *skb;
 
-	while ((skb = skb_peek(&sk->sk_write_queue))) {
+	while ((skb = dccp_qpolicy_top(sk))) {
 		int rc = ccid_hc_tx_send_packet(dp->dccps_hc_tx_ccid, sk, skb);
 
 		switch (ccid_packet_dequeue_eval(rc)) {

@@ -342,8 +342,7 @@ void dccp_write_xmit(struct sock *sk)
 			dccp_xmit_packet(sk);
 			break;
 		case CCID_PACKET_ERR:
-			skb_dequeue(&sk->sk_write_queue);
-			kfree_skb(skb);
+			dccp_qpolicy_drop(sk, skb);
 			dccp_pr_debug("packet discarded due to err=%d\n", rc);
 		}
 	}

include/linux/dccp.h +19 -0

@@ -195,6 +195,19 @@ enum dccp_feature_numbers {
 	DCCPF_MAX_CCID_SPECIFIC = 255,
 };
 
+/* DCCP socket control message types for cmsg */
+enum dccp_cmsg_type {
+	DCCP_SCM_PRIORITY = 1,
+	DCCP_SCM_MAX
+};
+
+/* DCCP priorities for outgoing/queued packets */
+enum dccp_packet_dequeueing_policy {
+	DCCPQ_POLICY_SIMPLE,
+	DCCPQ_POLICY_PRIO,
+	DCCPQ_POLICY_MAX
+};
+
 /* DCCP socket options */
 #define DCCP_SOCKOPT_PACKET_SIZE	1 /* XXX deprecated, without effect */
 #define DCCP_SOCKOPT_SERVICE		2

@@ -208,6 +221,8 @@ enum dccp_feature_numbers {
 #define DCCP_SOCKOPT_CCID		13
 #define DCCP_SOCKOPT_TX_CCID		14
 #define DCCP_SOCKOPT_RX_CCID		15
+#define DCCP_SOCKOPT_QPOLICY_ID		16
+#define DCCP_SOCKOPT_QPOLICY_TXQLEN	17
 #define DCCP_SOCKOPT_CCID_RX_INFO	128
 #define DCCP_SOCKOPT_CCID_TX_INFO	192

@@ -459,6 +474,8 @@ struct dccp_ackvec;
  * @dccps_hc_rx_ccid - CCID used for the receiver (or receiving half-connection)
  * @dccps_hc_tx_ccid - CCID used for the sender (or sending half-connection)
  * @dccps_options_received - parsed set of retrieved options
+ * @dccps_qpolicy - TX dequeueing policy, one of %dccp_packet_dequeueing_policy
+ * @dccps_tx_qlen - maximum length of the TX queue
  * @dccps_role - role of this sock, one of %dccp_role
  * @dccps_hc_rx_insert_options - receiver wants to add options when acking
  * @dccps_hc_tx_insert_options - sender wants to add options when sending

@@ -501,6 +518,8 @@ struct dccp_sock {
 	struct ccid			*dccps_hc_rx_ccid;
 	struct ccid			*dccps_hc_tx_ccid;
 	struct dccp_options_received	dccps_options_received;
+	__u8				dccps_qpolicy;
+	__u32				dccps_tx_qlen;
 	enum dccp_role			dccps_role:2;
 	__u8				dccps_hc_rx_insert_options:1;
 	__u8				dccps_hc_tx_insert_options:1;

net/dccp/proto.c +64 -3

103 lines not on this page · raw message

The University of Aberdeen is a charity registered in Scotland, No SC013683.

Tomasz Grobelny

2008-05-12 08:33 UTC #4 lore raw

Re: [PATCH 2/2] [RFT] [DCCP]: Policy-based packet dequeueing

Dnia Monday 12 of May 2008, napisa³e¶:

Quoted 9 lines

From: Tomasz Grobelny <[email protected]>
This patch adds a generic infrastructure for policy-based dequeueing of TX packets and provides two policies:
* a simple FIFO policy (which is the default) and
* a priority based policy (set via socket options).
Both policies honour the tx_qlen sysctl for the maximum size of the write queue (can be overridden via socket options).

Quoted 7 lines

The priority policy uses skb->priority internally to assign an u32 priority identifier, using the same ranking as SO_PRIORITY. The skb->priority field is set to 0 when the packet leaves DCCP. The priority is supplied as ancillary data using cmsg(3), the patch also provides the requisite parsing routines.
Signed-off-by Gerrit Renker <[email protected]>

Signed-off-by Tomasz Grobelny <[email protected]>

I hope that's how you sign off patches (I'm doing it for the first time).

Signature · 2 lines

Regards,
Tomasz Grobelny