L2CAP Flow Control

Hi everybody,

after some months of coding, testing, deadlocks, debugging, book-readings, etc. I present my first working version of L2CAP flow control for the BlueZ stack. This is an early alpha release and may contain errors -- but hey, it is the first really working version here so be lenient toward me :-)

I will now go over some of the details of my patch:

We start with four timer functions of which two correspond to the monitor timer and the retransmission timer respectively. Those four functions should be pretty self explanatory. In short we've got two starter functions and two signal handlers. Due to the lack of nice test cases I couldn't test the functionality of both timers as it occurs. The next function within the patch is the l2cap_init() function that got extended quite a bit to set proper configuration values for flow control mode, initialize the SKB TxQueue and both timers accordingly. The next part is of much more interest. The function l2cap_do_send_rfc() is used in combination with l2cap_segment_sdu() as a replacement for l2cap_do_send() in case of flow control mode. Both new functions are called from within l2cap_sock_sendmsg():

	if (l2cap_pi(sk)->mode == L2CAP_MODE_FLOW) {
		err = l2cap_segment_sdu(sk, msg, len);
		if (err < 0)
			goto out;
		if (l2cap_do_send_rfc(sk) < 0)
			err = -1;
	} else {
		err = l2cap_do_send(sk, msg, len);
	}

So at first l2cap_segment_sdu() is invoked. This is part of a sending procedure so in case we get a SDU from user space that is too big to fit into a single PDU of size MTU, we've got to split it into several smaller PDUs. The incoming argument len reflects the size of the message being sent, so at first we differentiate if this size fits into the MTU's configured size to build one single frame. If the size is greater we need to build segmented I-Frames. This procedure is closely related to the one implemented within the original l2cap_do_send() which works for B-Frames. But working in flow control mode with I- and S-Frames instead of B-Frames requires to use individual control fields (with individual send and receive sequence numbers etc.) and a unique frame check sequence per frame. Further more we need to make sure to send only as many frames as fit into the peer's receive buffer. Therefore we cannot use the scatter/gather i/o mechanism as far as I know. So in case the size is too long for one single frame, we prepare several I-Frames step by step and put them all into the send queue:

	skb_queue_tail(&l2cap_pi(sk)->tx_queue, skb);
If this is all done error-free we call l2cap_do_send_rfc() which checks
the occupied spaces in the peer's receive buffer and sends frames from
it's send queue accordingly:
	while ((pi->tx_queue_frames > 0) && (pi->otxw > occupied)) {
		skb = skb_dequeue(&pi->tx_queue);
		if (skb == NULL) {
			goto fail;
		}
		if ((err = hci_send_acl(conn->hcon, skb, 0)) < 0)
			goto fail;

		pi->tx_queue_frames--;
		occupied++;
	}

I will go over the following functions which are only used for the configuration process as I already explained them in detail some time ago.

The next generic function is l2cap_send_sframe() which is used to send S-Frames as acknowledgements. Nothing spectacular happens within this function -- it is like the transmission of I-Frames but much less complicated as we do not have any user input data to handle. The next function, l2cap_invalid_frame_detection() is the first of a series of functions which correspond to the reception part mainly. As the name suggests we check an incoming frame (no matter if I-Frame or S-Frame) for all the kinds of validity that are mentioned in the specification. I tried to sort the cause of errors according to the spec.
l2cap_process_txseq() and l2cap_process_reqseq() do what they are supposed to do: they check the corresponding bits in the control field of an incoming frame and adjust the socket's variables if appropriate. What comes next is another crucial function, l2cap_reassembly(), say the counter-part to l2cap_segment_sdu(). In this function -- which is called after all the different stages of error checking from within l2cap_data_channel on receiption of a frame -- we prepare the incoming frames to be reassembled into one final SDU.
Corresponding to the use of the SAR field we may have to take care of
the type of frame (i.e. START, END, CONTINUATION or UNSEGMENTED). I tried to implemented this functionality as clean and short as possible. Some of this code may be errorneous due to the lack of testing -- so some of this work should work at least theoretically. In case of an unsegmented SDU the steps are pretty much straight forward -- basically the information payload is checked out (sock_queue_rcv_skb()) and an S-Frame is sent as a response. Somewhat more complicated is the case in which we receive a bigger segmented SDU. In this case a new temporary socket buffer in the l2cap_pi(sk) struct is created and used to reassemble the SDU. Keep in mind and be always aware of the fact that flow control mode in the Bluetooth L2CAP layer does not contain any retransmission mechanisms. So in case of a lost frame, the final information payload that is passed to the user space is just not the one expected, but L2CAP doesn't care about it. Nevertheless I had to implement some error checking facilities that make sure that we are not crashing just by the absence of any specific frame.
Finally the l2cap_data_channel() has been extended. This is the starting point of this whole work if you check the comment of prior versions which has been erased ;-) So if we are in flow control mode, all the aforementioned functions are called in logical order.

That's basically it. Be aware of enough errors in this code to fill evenings with debugging sessions. This code works here by sending files from one patched linux computer to another patched one. Using the debug output you can verify that flow control is in action even though I couldn't create a test case in which you could really flood one peer with frames. This code has to be tested against all different kinds of devices and stacks as I had to make some modifications to the configuration process and some stacks have a very "sensitive" behaviour regarding this.
Feel free to test it and harden it with me. :-)

Bye,
Martin

diff -uNr linux-2.6.17-mh5/include/net/bluetooth/l2cap.h linux-2.6.17-mr/include/net/bluetooth/l2cap.h
@@ -27,7 +27,19 @@
 
 /* L2CAP defaults */
 #define L2CAP_DEFAULT_MTU	672
+#define L2CAP_MIN_MTU		48
 #define L2CAP_DEFAULT_FLUSH_TO	0xFFFF
+#define L2CAP_DEFAULT_TXW 	32
+#define L2CAP_MIN_TXW		1
+#define L2CAP_MAX_TXW		32
+#define L2CAP_DEFAULT_MAXT 	32
+#define L2CAP_DEFAULT_RETTO 	1000
+#define L2CAP_DEFAULT_MONTO 	1000
+#define L2CAP_DEFAULT_MPS 	65531
+#define L2CAP_MAX_MPS		65531
+
+/* maximum possible options for one request/response */
+#define L2CAP_MAX_OPTS 		128
 
 #define L2CAP_CONN_TIMEOUT	(HZ * 40)
 

@@ -47,6 +59,10 @@
 	__u8  mode;
 };
 
+#define L2CAP_MODE_BASIC	0x00
+#define L2CAP_MODE_RET		0x01
+#define L2CAP_MODE_FLOW		0x02
+
 #define L2CAP_CONNINFO	0x02
 struct l2cap_conninfo {
 	__u16 hci_handle;

@@ -76,32 +92,38 @@
 
 /* L2CAP structures */
 struct l2cap_hdr {
-	__u16      len;
-	__u16      cid;
+	__le16     len;
+	__le16     cid;
 } __attribute__ ((packed));
 #define L2CAP_HDR_SIZE		4
 
 struct l2cap_cmd_hdr {
 	__u8       code;
 	__u8       ident;
-	__u16      len;
+	__le16     len;
 } __attribute__ ((packed));
 #define L2CAP_CMD_HDR_SIZE	4
 
 struct l2cap_cmd_rej {
-	__u16      reason;
+	__le16     reason;
+	__le16     data[0];
 } __attribute__ ((packed));
 
+/* command reject reasons */
+#define L2CAP_CMD_NOT_UNDERSTOOD 	0x0000
+#define L2CAP_MTU_EXCEEDED 		0x0001
+#define L2CAP_INVALID_CID 		0x0002
+
 struct l2cap_conn_req {
-	__u16      psm;
-	__u16      scid;
+	__le16     psm;
+	__le16     scid;
 } __attribute__ ((packed));
 
 struct l2cap_conn_rsp {
-	__u16      dcid;
-	__u16      scid;
-	__u16      result;
-	__u16      status;
+	__le16     dcid;
+	__le16     scid;
+	__le16     result;
+	__le16     status;
 } __attribute__ ((packed));
 
 /* connect result */

@@ -117,20 +139,22 @@
 #define L2CAP_CS_AUTHOR_PEND  0x0002
 
 struct l2cap_conf_req {
-	__u16      dcid;
-	__u16      flags;
+	__le16     dcid;
+	__le16     flags;
 	__u8       data[0];
 } __attribute__ ((packed));
 
 struct l2cap_conf_rsp {
-	__u16      scid;
-	__u16      flags;
-	__u16      result;
+	__le16     scid;
+	__le16     flags;
+	__le16     result;
 	__u8       data[0];
 } __attribute__ ((packed));
 
-#define L2CAP_CONF_SUCCESS	0x00
-#define L2CAP_CONF_UNACCEPT	0x01
+#define L2CAP_CONF_SUCCESS	0x0000
+#define L2CAP_CONF_UNACCEPT	0x0001
+#define L2CAP_CONF_REJ		0x0002
+#define L2CAP_CONF_UNKNOWN	0x0003
 
 struct l2cap_conf_opt {
 	__u8       type;

@@ -146,34 +170,47 @@
 
 #define L2CAP_CONF_MAX_SIZE	22
 
+struct l2cap_conf_rfc {
+	__u8	mode;
+	__u8	txw;
+	__u8	maxt;
+	__le16	ret_to;
+	__le16	mon_to;
+	__le16	mps;
+} __attribute__ ((packed));
+
 struct l2cap_disconn_req {
-	__u16      dcid;
-	__u16      scid;
+	__le16     dcid;
+	__le16     scid;
 } __attribute__ ((packed));
 
 struct l2cap_disconn_rsp {
-	__u16      dcid;
-	__u16      scid;
+	__le16     dcid;
+	__le16     scid;
 } __attribute__ ((packed));
 
 struct l2cap_info_req {
-	__u16       type;
-	__u8        data[0];
+	__le16      type;
 } __attribute__ ((packed));
 
 struct l2cap_info_rsp {
-	__u16       type;
-	__u16       result;
+	__le16      type;
+	__le16      result;
 	__u8        data[0];
 } __attribute__ ((packed));
 
 /* info type */
-#define L2CAP_IT_CL_MTU     0x0001
-#define L2CAP_IT_FEAT_MASK  0x0002
+#define L2CAP_IT_CL_MTU		0x0001
+#define L2CAP_IT_FEAT_MASK	0x0002
+
+/* bits for extended features */
+#define L2CAP_EXT_FCM		0x0001
+#define L2CAP_EXT_RTM		0x0002
+#define L2CAP_EXT_QOS		0x0004
 
 /* info result */
-#define L2CAP_IR_SUCCESS    0x0000
-#define L2CAP_IR_NOTSUPP    0x0001
+#define L2CAP_IR_SUCCESS	0x0000
+#define L2CAP_IR_NOTSUPP	0x0001
 
 /* ----- L2CAP connections ----- */
 struct l2cap_chan_list {

@@ -205,33 +242,111 @@
 
 struct l2cap_pinfo {
 	struct bt_sock	bt;
-	__u16		psm;
+	__le16		psm;
+	__le16		sport;
 	__u16		dcid;
 	__u16		scid;
 
 	__u16		imtu;
 	__u16		omtu;
 	__u16		flush_to;
+	__u8		mode;
 
 	__u32		link_mode;
+	/* connectionless MTU size from info response */
+	__u16		info_mtu;
+	/* extended feature mask from info response */
+	__u32		info_ext;
 
-	__u8		conf_state;
+	/* bitmask for current config state */
+	__u16		conf_state;
 	__u8		conf_retry;
 	__u16		conf_mtu;
 
-	__u8		ident;
+	/* Configuration Request RFC Options */
+	__u8		conf_mode;
+	__u8		conf_txw;
+	__u8		conf_maxt;
+	__u16		conf_ret_to;
+	__u16		conf_mon_to;
+	__u16		conf_mps;
+
+	/* incoming RFC Options */
+	__u8		itxw;
+	__u8		imaxt;
+	__u16		iret_to;
+	__u16		imon_to;
+	__u16		imps;
+
+	/* outgoing RFC Options */
+	__u8		otxw;
+	__u8		omaxt;
+	__u16		oret_to;
+	__u16		omon_to;
+	__u16		omps;
+
+	/* flow control mode */
+	__u8		tx_seq;
+	__u8		next_txseq;
+	__u8		exp_ackseq;
+	__u8		req_seq;
+	__u8		exp_txseq;
+	__u8		buffer_seq;
+	__u16		sdu_len;
+	struct sk_buff	*sdu;
 
-	__u16		sport;
+	__u32			tx_queue_frames;
+	struct sk_buff_head 	tx_queue;
 
+	__u8		ident;
+
+	struct timer_list	ret_timer;
+	struct timer_list	mon_timer;
 	struct l2cap_conn	*conn;
 	struct sock		*next_c;
 	struct sock		*prev_c;
 };
 
-#define L2CAP_CONF_REQ_SENT    0x01
-#define L2CAP_CONF_INPUT_DONE  0x02
-#define L2CAP_CONF_OUTPUT_DONE 0x04
-#define L2CAP_CONF_MAX_RETRIES 2
+#define L2CAP_CONF_MAX_RETRIES	2
+
+/* different conf_states */
+#define L2CAP_INFO_REQ_SENT 	0x01
+#define L2CAP_CONF_REQ_SENT 	0x02
+#define L2CAP_CONF_INPUT_DONE	0x04
+#define L2CAP_CONF_OUTPUT_DONE	0x08
+#define L2CAP_CONF_UNACCEPT_MTU	0x10
+#define L2CAP_CONF_UNACCEPT_RFC	0x20
+#define L2CAP_INFO_INPUT_DONE	0x40
+
+/* RFC definitions */
+#define L2CAP_MAX_DATA_LEN	65531
+#define L2CAP_CONTROL_SIZE	2
+#define L2CAP_FCS_SIZE		2
+#define L2CAP_SFRAME_SIZE	8
+
+#define L2CAP_SAR_UNSEGMENTED	0x0000
+#define L2CAP_SAR_START		0x4000
+#define L2CAP_SAR_END		0x8000
+#define L2CAP_SAR_CONTINUE	0xC000
+#define L2CAP_SAR_MASK		0xC000
+#define L2CAP_TXSEQ_MASK	0x007E
+#define L2CAP_REQSEQ_MASK	0x3F00
+
+#define L2CAP_GET_TXSEQ(control)	((__le16_to_cpu(control) \
+			& L2CAP_TXSEQ_MASK) >> 1)
+#define L2CAP_GET_REQSEQ(control)	((__le16_to_cpu(control) \
+			& L2CAP_REQSEQ_MASK) >> 8)
+#define L2CAP_GET_SAR(control)		(__le16_to_cpu(control) & L2CAP_SAR_MASK)
+
+#define L2CAP_SET_TXSEQ(control, txseq) 	control = \
+			(__cpu_to_le16((txseq  << 1) & L2CAP_TXSEQ_MASK)) | \
+			(__cpu_to_le16(control) & ~L2CAP_TXSEQ_MASK)
+#define L2CAP_SET_REQSEQ(control, reqseq) 	control = \
+			(__cpu_to_le16((reqseq << 8) & L2CAP_REQSEQ_MASK)) | \
+			(__cpu_to_le16(control) & ~L2CAP_REQSEQ_MASK)
+#define L2CAP_SET_SAR(control, sar) 		control = \
+			(__cpu_to_le16(sar & L2CAP_SAR_MASK)) |           \
+			(__cpu_to_le16(control) & ~L2CAP_SAR_MASK)
 
 void l2cap_load(void);
 

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642

_______________________________________________
Bluez-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/bluez-devel

Hi Martin,

nice stuff and I decided to put out patch-2.6.17-mh6 with your patch included to open it for a wider testing audience. I will boot up my development system with this patch and see how it goes.

I haven't done any code review, but the obvious thing you missed is the "select CRC16" in the Kconfig file.

The rumors have it that the Symbian OS 9.1 already supports L2CAP retransmission and flow control (RFC) and this might be a good testing system.

Keep up the good work.

Regards

Marcel

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Bluez-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/bluez-devel