[PATCHv3 0/2] ERTM state machine changes, part 1

[PATCHv3 0/2] ERTM state machine changes, part 1

[Mat Martineau]

This is the first of several patch series to rework the ERTM state
machine.

PATCHv1: Four patches, two patches updating header files were merged
PATCHv2: Reworked utility functions for seq_lists and control headers
PATCHv3: Removed extra debug output, added error handling for
  allocation failure, used some long lines at Marcel's request, removed
  an unnecessary variable, and added a __set_control function.

Mat Martineau (2):
  Bluetooth: Add the l2cap_seq_list structure for tracking frames
    (Acked-by Marcel last time, but added new error handling code)
  Bluetooth: Functions for handling ERTM control fields

 include/net/bluetooth/l2cap.h |   12 ++
 net/bluetooth/l2cap_core.c    |  251 +++++++++++++++++++++++++++++++++++++++--
 2 files changed, 255 insertions(+), 8 deletions(-)

-- 
1.7.9.4

--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum

[PATCHv3 1/2] Bluetooth: Add the l2cap_seq_list structure for tracking frames

[Mat Martineau]

A sequence list is a data structure used to track frames that need to
be retransmitted, and frames that have been requested for
retransmission by the remote device.  It can compactly represent a
list of sequence numbers within the ERTM transmit window.  Memory for
the list is allocated once at connection time, and common operations
in ERTM are O(1).

Signed-off-by: Mat Martineau <mathewm@codeaurora.org>
---
 include/net/bluetooth/l2cap.h |   12 ++++
 net/bluetooth/l2cap_core.c    |  152 ++++++++++++++++++++++++++++++++++++++---
 2 files changed, 156 insertions(+), 8 deletions(-)

diff --git a/include/net/bluetooth/l2cap.h b/include/net/bluetooth/l2cap.h
index f6f0500..5d65b3d 100644
--- a/include/net/bluetooth/l2cap.h
+++ b/include/net/bluetooth/l2cap.h
@@ -407,6 +407,16 @@ struct l2cap_conn_param_update_rsp {
 #define L2CAP_CONN_PARAM_REJECTED	0x0001
 
 /* ----- L2CAP channels and connections ----- */
+struct l2cap_seq_list {
+	__u16	head;
+	__u16	tail;
+	__u16	mask;
+	__u16	*list;
+};
+
+#define L2CAP_SEQ_LIST_CLEAR	0xFFFF
+#define L2CAP_SEQ_LIST_TAIL	0x8000
+
 struct srej_list {
 	__u16	tx_seq;
 	struct list_head list;
@@ -501,6 +511,8 @@ struct l2cap_chan {
 	struct sk_buff		*tx_send_head;
 	struct sk_buff_head	tx_q;
 	struct sk_buff_head	srej_q;
+	struct l2cap_seq_list	srej_list;
+	struct l2cap_seq_list	retrans_list;
 	struct list_head	srej_l;
 
 	struct list_head	list;
diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
index 3caff27..650e9f5 100644
--- a/net/bluetooth/l2cap_core.c
+++ b/net/bluetooth/l2cap_core.c
@@ -233,6 +233,125 @@ static inline void l2cap_chan_set_err(struct l2cap_chan *chan, int err)
 	release_sock(sk);
 }
 
+/* ---- L2CAP sequence number lists ---- */
+
+/* For ERTM, ordered lists of sequence numbers must be tracked for
+ * SREJ requests that are received and for frames that are to be
+ * retransmitted. These seq_list functions implement a singly-linked
+ * list in an array, where membership in the list can also be checked
+ * in constant time. Items can also be added to the tail of the list
+ * and removed from the head in constant time, without further memory
+ * allocs or frees.
+ */
+
+static int l2cap_seq_list_init(struct l2cap_seq_list *seq_list, u16 size)
+{
+	u16 alloc_size = 1;
+	int i;
+
+	/* Allocated size is a power of 2 to map sequence numbers
+	 * (which may be up to 14 bits) in to a smaller array that is
+	 * sized for the negotiated ERTM transmit windows.
+	 */
+	while (alloc_size && alloc_size <= size)
+		alloc_size <<= 1;
+	if (!alloc_size)
+		return -ENOMEM;
+
+	seq_list->list = kzalloc(sizeof(u16) * alloc_size, GFP_KERNEL);
+	if (!seq_list->list)
+		return -ENOMEM;
+
+	seq_list->mask = alloc_size - 1;
+	seq_list->head = L2CAP_SEQ_LIST_CLEAR;
+	seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
+	for (i = 0; i < alloc_size; i++)
+		seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
+
+	return 0;
+}
+
+static inline void l2cap_seq_list_free(struct l2cap_seq_list *seq_list)
+{
+	kfree(seq_list->list);
+}
+
+static inline bool l2cap_seq_list_contains(struct l2cap_seq_list *seq_list,
+					   u16 seq)
+{
+	/* Constant-time check for list membership */
+	return seq_list->list[seq & seq_list->mask] != L2CAP_SEQ_LIST_CLEAR;
+}
+
+static u16 l2cap_seq_list_remove(struct l2cap_seq_list *seq_list, u16 seq)
+{
+	u16 mask = seq_list->mask;
+
+	if (seq_list->head == L2CAP_SEQ_LIST_CLEAR) {
+		/* In case someone tries to pop the head of an empty list */
+		return L2CAP_SEQ_LIST_CLEAR;
+	} else if (seq_list->head == seq) {
+		/* Head can be removed in constant time */
+		seq_list->head = seq_list->list[seq & mask];
+		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
+
+		if (seq_list->head == L2CAP_SEQ_LIST_TAIL) {
+			seq_list->head = L2CAP_SEQ_LIST_CLEAR;
+			seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
+		}
+	} else {
+		/* Walk the list to find the sequence number */
+		u16 prev = seq_list->head;
+		while (seq_list->list[prev & mask] != seq) {
+			prev = seq_list->list[prev & mask];
+			if (prev == L2CAP_SEQ_LIST_TAIL)
+				return L2CAP_SEQ_LIST_CLEAR;
+		}
+
+		/* Unlink the number from the list and clear it */
+		seq_list->list[prev & mask] = seq_list->list[seq & mask];
+		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
+		if (seq_list->tail == seq)
+			seq_list->tail = prev;
+	}
+	return seq;
+}
+
+static u16 l2cap_seq_list_pop(struct l2cap_seq_list *seq_list)
+{
+	/* Remove the head in constant time */
+	return l2cap_seq_list_remove(seq_list, seq_list->head);
+}
+
+static void l2cap_seq_list_clear(struct l2cap_seq_list *seq_list)
+{
+	if (seq_list->head != L2CAP_SEQ_LIST_CLEAR) {
+		u16 i;
+		for (i = 0; i <= seq_list->mask; i++)
+			seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
+
+		seq_list->head = L2CAP_SEQ_LIST_CLEAR;
+		seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
+	}
+}
+
+static void l2cap_seq_list_append(struct l2cap_seq_list *seq_list, u16 seq)
+{
+	u16 mask = seq_list->mask;
+
+	/* All appends happen in constant time */
+
+	if (seq_list->list[seq & mask] == L2CAP_SEQ_LIST_CLEAR) {
+		if (seq_list->tail == L2CAP_SEQ_LIST_CLEAR)
+			seq_list->head = seq;
+		else
+			seq_list->list[seq_list->tail & mask] = seq;
+
+		seq_list->tail = seq;
+		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_TAIL;
+	}
+}
+
 static void l2cap_chan_timeout(struct work_struct *work)
 {
 	struct l2cap_chan *chan = container_of(work, struct l2cap_chan,
@@ -404,6 +523,8 @@ static void l2cap_chan_del(struct l2cap_chan *chan, int err)
 
 		skb_queue_purge(&chan->srej_q);
 
+		l2cap_seq_list_free(&chan->srej_list);
+		l2cap_seq_list_free(&chan->retrans_list);
 		list_for_each_entry_safe(l, tmp, &chan->srej_l, list) {
 			list_del(&l->list);
 			kfree(l);
@@ -2038,8 +2159,10 @@ static void l2cap_ack_timeout(struct work_struct *work)
 	l2cap_chan_put(chan);
 }
 
-static inline void l2cap_ertm_init(struct l2cap_chan *chan)
+static inline int l2cap_ertm_init(struct l2cap_chan *chan)
 {
+	int err;
+
 	chan->expected_ack_seq = 0;
 	chan->unacked_frames = 0;
 	chan->buffer_seq = 0;
@@ -2053,6 +2176,11 @@ static inline void l2cap_ertm_init(struct l2cap_chan *chan)
 	skb_queue_head_init(&chan->srej_q);
 
 	INIT_LIST_HEAD(&chan->srej_l);
+	err = l2cap_seq_list_init(&chan->srej_list, chan->tx_win);
+	if (err < 0)
+		return err;
+
+	return l2cap_seq_list_init(&chan->retrans_list, chan->remote_tx_win);
 }
 
 static inline __u8 l2cap_select_mode(__u8 mode, __u16 remote_feat_mask)
@@ -2846,7 +2974,7 @@ static inline int l2cap_config_req(struct l2cap_conn *conn, struct l2cap_cmd_hdr
 	u16 dcid, flags;
 	u8 rsp[64];
 	struct l2cap_chan *chan;
-	int len;
+	int len, err = 0;
 
 	dcid  = __le16_to_cpu(req->dcid);
 	flags = __le16_to_cpu(req->flags);
@@ -2917,9 +3045,13 @@ static inline int l2cap_config_req(struct l2cap_conn *conn, struct l2cap_cmd_hdr
 		chan->expected_tx_seq = 0;
 		skb_queue_head_init(&chan->tx_q);
 		if (chan->mode == L2CAP_MODE_ERTM)
-			l2cap_ertm_init(chan);
+			err = l2cap_ertm_init(chan);
+
+		if (err < 0)
+			l2cap_send_disconn_req(chan->conn, chan, -err);
+		else
+			l2cap_chan_ready(chan);
 
-		l2cap_chan_ready(chan);
 		goto unlock;
 	}
 
@@ -2947,7 +3079,7 @@ static inline int l2cap_config_req(struct l2cap_conn *conn, struct l2cap_cmd_hdr
 
 unlock:
 	l2cap_chan_unlock(chan);
-	return 0;
+	return err;
 }
 
 static inline int l2cap_config_rsp(struct l2cap_conn *conn, struct l2cap_cmd_hdr *cmd, u8 *data)
@@ -2956,6 +3088,7 @@ static inline int l2cap_config_rsp(struct l2cap_conn *conn, struct l2cap_cmd_hdr
 	u16 scid, flags, result;
 	struct l2cap_chan *chan;
 	int len = le16_to_cpu(cmd->len) - sizeof(*rsp);
+	int err = 0;
 
 	scid   = __le16_to_cpu(rsp->scid);
 	flags  = __le16_to_cpu(rsp->flags);
@@ -3047,14 +3180,17 @@ static inline int l2cap_config_rsp(struct l2cap_conn *conn, struct l2cap_cmd_hdr
 		chan->expected_tx_seq = 0;
 		skb_queue_head_init(&chan->tx_q);
 		if (chan->mode ==  L2CAP_MODE_ERTM)
-			l2cap_ertm_init(chan);
+			err = l2cap_ertm_init(chan);
 
-		l2cap_chan_ready(chan);
+		if (err < 0)
+			l2cap_send_disconn_req(chan->conn, chan, -err);
+		else
+			l2cap_chan_ready(chan);
 	}
 
 done:
 	l2cap_chan_unlock(chan);
-	return 0;
+	return err;
 }
 
 static inline int l2cap_disconnect_req(struct l2cap_conn *conn, struct l2cap_cmd_hdr *cmd, u8 *data)
-- 
1.7.9.4

--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum

[PATCHv3 2/2] Bluetooth: Functions for handling ERTM control fields

[Mat Martineau]

These functions encode or decode ERTM control fields (extended or
enhanced) to or from the new l2cap_ctrl structure.

Signed-off-by: Mat Martineau <mathewm@codeaurora.org>
---
 net/bluetooth/l2cap_core.c |   99 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 99 insertions(+)

diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
index 650e9f5..b1eac5a 100644
--- a/net/bluetooth/l2cap_core.c
+++ b/net/bluetooth/l2cap_core.c
@@ -780,6 +780,103 @@ static inline void l2cap_send_rr_or_rnr(struct l2cap_chan *chan, u32 control)
 	l2cap_send_sframe(chan, control);
 }
 
+static u16 __pack_enhanced_control(struct l2cap_ctrl *control)
+{
+	u16 packed;
+
+	packed = control->reqseq << L2CAP_CTRL_REQSEQ_SHIFT;
+	packed |= control->final << L2CAP_CTRL_FINAL_SHIFT;
+
+	if (control->sframe) {
+		packed |= control->poll << L2CAP_CTRL_POLL_SHIFT;
+		packed |= control->super << L2CAP_CTRL_SUPER_SHIFT;
+		packed |= L2CAP_CTRL_FRAME_TYPE;
+	} else {
+		packed |= control->sar << L2CAP_CTRL_SAR_SHIFT;
+		packed |= control->txseq << L2CAP_CTRL_TXSEQ_SHIFT;
+	}
+
+	return packed;
+}
+
+static void __get_enhanced_control(u16 enh, struct l2cap_ctrl *control)
+{
+	control->reqseq = (enh & L2CAP_CTRL_REQSEQ) >> L2CAP_CTRL_REQSEQ_SHIFT;
+	control->final = (enh & L2CAP_CTRL_FINAL) >> L2CAP_CTRL_FINAL_SHIFT;
+
+	if (enh & L2CAP_CTRL_FRAME_TYPE) {
+		/* S-Frame */
+		control->sframe = 1;
+		control->poll = (enh & L2CAP_CTRL_POLL) >> L2CAP_CTRL_POLL_SHIFT;
+		control->super = (enh & L2CAP_CTRL_SUPERVISE) >> L2CAP_CTRL_SUPER_SHIFT;
+
+		control->sar = 0;
+		control->txseq = 0;
+	} else {
+		/* I-Frame */
+		control->sframe = 0;
+		control->sar = (enh & L2CAP_CTRL_SAR) >> L2CAP_CTRL_SAR_SHIFT;
+		control->txseq = (enh & L2CAP_CTRL_TXSEQ) >> L2CAP_CTRL_TXSEQ_SHIFT;
+
+		control->poll = 0;
+		control->super = 0;
+	}
+}
+
+static u32 __pack_extended_control(struct l2cap_ctrl *control)
+{
+	u32 packed;
+
+	packed = control->reqseq << L2CAP_EXT_CTRL_REQSEQ_SHIFT;
+	packed |= control->final << L2CAP_EXT_CTRL_FINAL_SHIFT;
+
+	if (control->sframe) {
+		packed |= control->poll << L2CAP_EXT_CTRL_POLL_SHIFT;
+		packed |= control->super << L2CAP_EXT_CTRL_SUPER_SHIFT;
+		packed |= L2CAP_EXT_CTRL_FRAME_TYPE;
+	} else {
+		packed |= control->sar << L2CAP_EXT_CTRL_SAR_SHIFT;
+		packed |= control->txseq << L2CAP_EXT_CTRL_TXSEQ_SHIFT;
+	}
+
+	return packed;
+}
+
+static void __get_extended_control(u32 ext, struct l2cap_ctrl *control)
+{
+	control->reqseq = (ext & L2CAP_EXT_CTRL_REQSEQ) >> L2CAP_EXT_CTRL_REQSEQ_SHIFT;
+	control->final = (ext & L2CAP_EXT_CTRL_FINAL) >> L2CAP_EXT_CTRL_FINAL_SHIFT;
+
+	if (ext & L2CAP_EXT_CTRL_FRAME_TYPE) {
+		/* S-Frame */
+		control->sframe = 1;
+		control->poll = (ext & L2CAP_EXT_CTRL_POLL) >> L2CAP_EXT_CTRL_POLL_SHIFT;
+		control->super = (ext & L2CAP_EXT_CTRL_SUPERVISE) >> L2CAP_EXT_CTRL_SUPER_SHIFT;
+
+		control->sar = 0;
+		control->txseq = 0;
+	} else {
+		/* I-Frame */
+		control->sframe = 0;
+		control->sar = (ext & L2CAP_EXT_CTRL_SAR) >> L2CAP_EXT_CTRL_SAR_SHIFT;
+		control->txseq = (ext & L2CAP_EXT_CTRL_TXSEQ) >> L2CAP_EXT_CTRL_TXSEQ_SHIFT;
+
+		control->poll = 0;
+		control->super = 0;
+	}
+}
+
+static void __set_control(struct l2cap_chan *chan, struct sk_buff *skb)
+{
+	if (test_bit(FLAG_EXT_CTRL, &chan->flags)) {
+		__get_extended_control(get_unaligned_le32(skb->data),
+				       &bt_cb(skb)->control);
+	} else {
+		__get_enhanced_control(get_unaligned_le16(skb->data),
+				       &bt_cb(skb)->control);
+	}
+}
+
 static inline int __l2cap_no_conn_pending(struct l2cap_chan *chan)
 {
 	return !test_bit(CONF_CONNECT_PEND, &chan->conf_state);
@@ -4354,6 +4451,8 @@ static int l2cap_ertm_data_rcv(struct l2cap_chan *chan, struct sk_buff *skb)
 	u16 req_seq;
 	int len, next_tx_seq_offset, req_seq_offset;
 
+	__set_control(chan, skb);
+
 	control = __get_control(chan, skb->data);
 	skb_pull(skb, __ctrl_size(chan));
 	len = skb->len;
-- 
1.7.9.4

--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum

Re: [PATCHv3 2/2] Bluetooth: Functions for handling ERTM control fields

[Andrei Emeltchenko]

Hi Mat,

On Tue, Apr 03, 2012 at 03:48:52PM -0700, Mat Martineau wrote:
> These functions encode or decode ERTM control fields (extended or
> enhanced) to or from the new l2cap_ctrl structure.
> 
> Signed-off-by: Mat Martineau <mathewm@codeaurora.org>

Looks good now.

Acked-by: Andrei Emeltchenko <andrei.emeltchenko@intel.com>


> ---
>  net/bluetooth/l2cap_core.c |   99 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 99 insertions(+)
> 
> diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
> index 650e9f5..b1eac5a 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -780,6 +780,103 @@ static inline void l2cap_send_rr_or_rnr(struct l2cap_chan *chan, u32 control)
>  	l2cap_send_sframe(chan, control);
>  }
>  
> +static u16 __pack_enhanced_control(struct l2cap_ctrl *control)
> +{
> +	u16 packed;
> +
> +	packed = control->reqseq << L2CAP_CTRL_REQSEQ_SHIFT;
> +	packed |= control->final << L2CAP_CTRL_FINAL_SHIFT;
> +
> +	if (control->sframe) {
> +		packed |= control->poll << L2CAP_CTRL_POLL_SHIFT;
> +		packed |= control->super << L2CAP_CTRL_SUPER_SHIFT;
> +		packed |= L2CAP_CTRL_FRAME_TYPE;
> +	} else {
> +		packed |= control->sar << L2CAP_CTRL_SAR_SHIFT;
> +		packed |= control->txseq << L2CAP_CTRL_TXSEQ_SHIFT;
> +	}
> +
> +	return packed;
> +}
> +
> +static void __get_enhanced_control(u16 enh, struct l2cap_ctrl *control)
> +{
> +	control->reqseq = (enh & L2CAP_CTRL_REQSEQ) >> L2CAP_CTRL_REQSEQ_SHIFT;
> +	control->final = (enh & L2CAP_CTRL_FINAL) >> L2CAP_CTRL_FINAL_SHIFT;
> +
> +	if (enh & L2CAP_CTRL_FRAME_TYPE) {
> +		/* S-Frame */
> +		control->sframe = 1;
> +		control->poll = (enh & L2CAP_CTRL_POLL) >> L2CAP_CTRL_POLL_SHIFT;
> +		control->super = (enh & L2CAP_CTRL_SUPERVISE) >> L2CAP_CTRL_SUPER_SHIFT;
> +
> +		control->sar = 0;
> +		control->txseq = 0;
> +	} else {
> +		/* I-Frame */
> +		control->sframe = 0;
> +		control->sar = (enh & L2CAP_CTRL_SAR) >> L2CAP_CTRL_SAR_SHIFT;
> +		control->txseq = (enh & L2CAP_CTRL_TXSEQ) >> L2CAP_CTRL_TXSEQ_SHIFT;
> +
> +		control->poll = 0;
> +		control->super = 0;
> +	}
> +}
> +
> +static u32 __pack_extended_control(struct l2cap_ctrl *control)
> +{
> +	u32 packed;
> +
> +	packed = control->reqseq << L2CAP_EXT_CTRL_REQSEQ_SHIFT;
> +	packed |= control->final << L2CAP_EXT_CTRL_FINAL_SHIFT;
> +
> +	if (control->sframe) {
> +		packed |= control->poll << L2CAP_EXT_CTRL_POLL_SHIFT;
> +		packed |= control->super << L2CAP_EXT_CTRL_SUPER_SHIFT;
> +		packed |= L2CAP_EXT_CTRL_FRAME_TYPE;
> +	} else {
> +		packed |= control->sar << L2CAP_EXT_CTRL_SAR_SHIFT;
> +		packed |= control->txseq << L2CAP_EXT_CTRL_TXSEQ_SHIFT;
> +	}
> +
> +	return packed;
> +}
> +
> +static void __get_extended_control(u32 ext, struct l2cap_ctrl *control)
> +{
> +	control->reqseq = (ext & L2CAP_EXT_CTRL_REQSEQ) >> L2CAP_EXT_CTRL_REQSEQ_SHIFT;
> +	control->final = (ext & L2CAP_EXT_CTRL_FINAL) >> L2CAP_EXT_CTRL_FINAL_SHIFT;
> +
> +	if (ext & L2CAP_EXT_CTRL_FRAME_TYPE) {
> +		/* S-Frame */
> +		control->sframe = 1;
> +		control->poll = (ext & L2CAP_EXT_CTRL_POLL) >> L2CAP_EXT_CTRL_POLL_SHIFT;
> +		control->super = (ext & L2CAP_EXT_CTRL_SUPERVISE) >> L2CAP_EXT_CTRL_SUPER_SHIFT;
> +
> +		control->sar = 0;
> +		control->txseq = 0;
> +	} else {
> +		/* I-Frame */
> +		control->sframe = 0;
> +		control->sar = (ext & L2CAP_EXT_CTRL_SAR) >> L2CAP_EXT_CTRL_SAR_SHIFT;
> +		control->txseq = (ext & L2CAP_EXT_CTRL_TXSEQ) >> L2CAP_EXT_CTRL_TXSEQ_SHIFT;
> +
> +		control->poll = 0;
> +		control->super = 0;
> +	}
> +}
> +
> +static void __set_control(struct l2cap_chan *chan, struct sk_buff *skb)
> +{
> +	if (test_bit(FLAG_EXT_CTRL, &chan->flags)) {
> +		__get_extended_control(get_unaligned_le32(skb->data),
> +				       &bt_cb(skb)->control);
> +	} else {
> +		__get_enhanced_control(get_unaligned_le16(skb->data),
> +				       &bt_cb(skb)->control);
> +	}
> +}
> +
>  static inline int __l2cap_no_conn_pending(struct l2cap_chan *chan)
>  {
>  	return !test_bit(CONF_CONNECT_PEND, &chan->conf_state);
> @@ -4354,6 +4451,8 @@ static int l2cap_ertm_data_rcv(struct l2cap_chan *chan, struct sk_buff *skb)
>  	u16 req_seq;
>  	int len, next_tx_seq_offset, req_seq_offset;
>  
> +	__set_control(chan, skb);
> +
>  	control = __get_control(chan, skb->data);
>  	skb_pull(skb, __ctrl_size(chan));
>  	len = skb->len;
> -- 
> 1.7.9.4
> 
> --
> Mat Martineau
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bluetooth" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCHv3 1/2] Bluetooth: Add the l2cap_seq_list structure for tracking frames

[Szymon Janc]

Hi Mat,

> A sequence list is a data structure used to track frames that need to
> be retransmitted, and frames that have been requested for
> retransmission by the remote device.  It can compactly represent a
> list of sequence numbers within the ERTM transmit window.  Memory for
> the list is allocated once at connection time, and common operations
> in ERTM are O(1).
> 
> Signed-off-by: Mat Martineau <mathewm@codeaurora.org>
> ---
>  include/net/bluetooth/l2cap.h |   12 ++++
>  net/bluetooth/l2cap_core.c    |  152 ++++++++++++++++++++++++++++++++++++++---
>  2 files changed, 156 insertions(+), 8 deletions(-)
> 
> diff --git a/include/net/bluetooth/l2cap.h b/include/net/bluetooth/l2cap.h
> index f6f0500..5d65b3d 100644
> --- a/include/net/bluetooth/l2cap.h
> +++ b/include/net/bluetooth/l2cap.h
> @@ -407,6 +407,16 @@ struct l2cap_conn_param_update_rsp {
>  #define L2CAP_CONN_PARAM_REJECTED	0x0001
>  
>  /* ----- L2CAP channels and connections ----- */
> +struct l2cap_seq_list {
> +	__u16	head;
> +	__u16	tail;
> +	__u16	mask;
> +	__u16	*list;
> +};
> +
> +#define L2CAP_SEQ_LIST_CLEAR	0xFFFF
> +#define L2CAP_SEQ_LIST_TAIL	0x8000
> +
>  struct srej_list {
>  	__u16	tx_seq;
>  	struct list_head list;
> @@ -501,6 +511,8 @@ struct l2cap_chan {
>  	struct sk_buff		*tx_send_head;
>  	struct sk_buff_head	tx_q;
>  	struct sk_buff_head	srej_q;
> +	struct l2cap_seq_list	srej_list;
> +	struct l2cap_seq_list	retrans_list;
>  	struct list_head	srej_l;
>  
>  	struct list_head	list;
> diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
> index 3caff27..650e9f5 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -233,6 +233,125 @@ static inline void l2cap_chan_set_err(struct l2cap_chan *chan, int err)
>  	release_sock(sk);
>  }
>  
> +/* ---- L2CAP sequence number lists ---- */
> +
> +/* For ERTM, ordered lists of sequence numbers must be tracked for
> + * SREJ requests that are received and for frames that are to be
> + * retransmitted. These seq_list functions implement a singly-linked
> + * list in an array, where membership in the list can also be checked
> + * in constant time. Items can also be added to the tail of the list
> + * and removed from the head in constant time, without further memory
> + * allocs or frees.
> + */
> +
> +static int l2cap_seq_list_init(struct l2cap_seq_list *seq_list, u16 size)
> +{
> +	u16 alloc_size = 1;
> +	int i;
> +
> +	/* Allocated size is a power of 2 to map sequence numbers
> +	 * (which may be up to 14 bits) in to a smaller array that is
> +	 * sized for the negotiated ERTM transmit windows.
> +	 */
> +	while (alloc_size && alloc_size <= size)
> +		alloc_size <<= 1;
> +	if (!alloc_size)
> +		return -ENOMEM;
> +

Is it intended that if size is already equal to power of two you still double it?
And maybe use roundup_pow_of_two macro here?

> +	seq_list->list = kzalloc(sizeof(u16) * alloc_size, GFP_KERNEL);
> +	if (!seq_list->list)
> +		return -ENOMEM;
> +
> +	seq_list->mask = alloc_size - 1;
> +	seq_list->head = L2CAP_SEQ_LIST_CLEAR;
> +	seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
> +	for (i = 0; i < alloc_size; i++)
> +		seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;

Could use memset for this instead of loop, and maybe use kcalloc instead of
kzalloc to allocate array?

> +
> +	return 0;
> +}
> +
> +static inline void l2cap_seq_list_free(struct l2cap_seq_list *seq_list)
> +{
> +	kfree(seq_list->list);
> +}
> +
> +static inline bool l2cap_seq_list_contains(struct l2cap_seq_list *seq_list,
> +					   u16 seq)
> +{
> +	/* Constant-time check for list membership */
> +	return seq_list->list[seq & seq_list->mask] != L2CAP_SEQ_LIST_CLEAR;
> +}
> +
> +static u16 l2cap_seq_list_remove(struct l2cap_seq_list *seq_list, u16 seq)
> +{
> +	u16 mask = seq_list->mask;
> +
> +	if (seq_list->head == L2CAP_SEQ_LIST_CLEAR) {
> +		/* In case someone tries to pop the head of an empty list */
> +		return L2CAP_SEQ_LIST_CLEAR;
> +	} else if (seq_list->head == seq) {
> +		/* Head can be removed in constant time */
> +		seq_list->head = seq_list->list[seq & mask];
> +		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
> +
> +		if (seq_list->head == L2CAP_SEQ_LIST_TAIL) {
> +			seq_list->head = L2CAP_SEQ_LIST_CLEAR;
> +			seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
> +		}
> +	} else {
> +		/* Walk the list to find the sequence number */
> +		u16 prev = seq_list->head;
> +		while (seq_list->list[prev & mask] != seq) {
> +			prev = seq_list->list[prev & mask];
> +			if (prev == L2CAP_SEQ_LIST_TAIL)
> +				return L2CAP_SEQ_LIST_CLEAR;
> +		}
> +
> +		/* Unlink the number from the list and clear it */
> +		seq_list->list[prev & mask] = seq_list->list[seq & mask];
> +		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
> +		if (seq_list->tail == seq)
> +			seq_list->tail = prev;
> +	}
> +	return seq;
> +}
> +
> +static u16 l2cap_seq_list_pop(struct l2cap_seq_list *seq_list)
> +{
> +	/* Remove the head in constant time */
> +	return l2cap_seq_list_remove(seq_list, seq_list->head);
> +}
> +
> +static void l2cap_seq_list_clear(struct l2cap_seq_list *seq_list)
> +{
> +	if (seq_list->head != L2CAP_SEQ_LIST_CLEAR) {
> +		u16 i;
> +		for (i = 0; i <= seq_list->mask; i++)
> +			seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;

maybe use memset?

-- 
BR
Szymon Janc

Re: [PATCHv3 1/2] Bluetooth: Add the l2cap_seq_list structure for tracking frames

[Andrei Emeltchenko]

Hi Szymon,

On Wed, Apr 04, 2012 at 10:44:19AM +0200, Szymon Janc wrote:
> > +	seq_list->list = kzalloc(sizeof(u16) * alloc_size, GFP_KERNEL);
> > +	if (!seq_list->list)
> > +		return -ENOMEM;
> > +
> > +	seq_list->mask = alloc_size - 1;
> > +	seq_list->head = L2CAP_SEQ_LIST_CLEAR;
> > +	seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
> > +	for (i = 0; i < alloc_size; i++)
> > +		seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
> 
> Could use memset for this instead of loop, and maybe use kcalloc instead of
> kzalloc to allocate array?

memset is implemented trough the loop anyway and would take 2x more
iterations.

void *memset(void *s, int c, size_t count)
{
	char *xs = s;
	while (count--)
		*xs++ = c;
	return s;
}



Best regards 
Andrei Emeltchenko 

Re: [PATCHv3 1/2] Bluetooth: Add the l2cap_seq_list structure for tracking frames

[Szymon Janc]

Hi,

> Hi Szymon,
> 
> On Wed, Apr 04, 2012 at 10:44:19AM +0200, Szymon Janc wrote:
> > > +	seq_list->list = kzalloc(sizeof(u16) * alloc_size, GFP_KERNEL);
> > > +	if (!seq_list->list)
> > > +		return -ENOMEM;
> > > +
> > > +	seq_list->mask = alloc_size - 1;
> > > +	seq_list->head = L2CAP_SEQ_LIST_CLEAR;
> > > +	seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
> > > +	for (i = 0; i < alloc_size; i++)
> > > +		seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
> > 
> > Could use memset for this instead of loop, and maybe use kcalloc instead of
> > kzalloc to allocate array?
> 
> memset is implemented trough the loop anyway and would take 2x more
> iterations.
> 
> void *memset(void *s, int c, size_t count)
> {
> 	char *xs = s;
> 	while (count--)
> 		*xs++ = c;
> 	return s;
> }

This is generic implementation, isn't it? There are some arch specific
implementation in arch/ as well and those should be a bit more efficient
comparing to loop...

-- 
Szymon Janc

Re: [PATCHv3 1/2] Bluetooth: Add the l2cap_seq_list structure for tracking frames

[Mat Martineau]

Hi Szymon -

On Wed, 4 Apr 2012, Szymon Janc wrote:

> Hi Mat,
>
>> A sequence list is a data structure used to track frames that need to
>> be retransmitted, and frames that have been requested for
>> retransmission by the remote device.  It can compactly represent a
>> list of sequence numbers within the ERTM transmit window.  Memory for
>> the list is allocated once at connection time, and common operations
>> in ERTM are O(1).
>>
>> Signed-off-by: Mat Martineau <mathewm@codeaurora.org>
>> ---
>>  include/net/bluetooth/l2cap.h |   12 ++++
>>  net/bluetooth/l2cap_core.c    |  152 ++++++++++++++++++++++++++++++++++++++---
>>  2 files changed, 156 insertions(+), 8 deletions(-)
>>
>> diff --git a/include/net/bluetooth/l2cap.h b/include/net/bluetooth/l2cap.h
>> index f6f0500..5d65b3d 100644
>> --- a/include/net/bluetooth/l2cap.h
>> +++ b/include/net/bluetooth/l2cap.h
>> @@ -407,6 +407,16 @@ struct l2cap_conn_param_update_rsp {
>>  #define L2CAP_CONN_PARAM_REJECTED	0x0001
>>
>>  /* ----- L2CAP channels and connections ----- */
>> +struct l2cap_seq_list {
>> +	__u16	head;
>> +	__u16	tail;
>> +	__u16	mask;
>> +	__u16	*list;
>> +};
>> +
>> +#define L2CAP_SEQ_LIST_CLEAR	0xFFFF
>> +#define L2CAP_SEQ_LIST_TAIL	0x8000
>> +
>>  struct srej_list {
>>  	__u16	tx_seq;
>>  	struct list_head list;
>> @@ -501,6 +511,8 @@ struct l2cap_chan {
>>  	struct sk_buff		*tx_send_head;
>>  	struct sk_buff_head	tx_q;
>>  	struct sk_buff_head	srej_q;
>> +	struct l2cap_seq_list	srej_list;
>> +	struct l2cap_seq_list	retrans_list;
>>  	struct list_head	srej_l;
>>
>>  	struct list_head	list;
>> diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
>> index 3caff27..650e9f5 100644
>> --- a/net/bluetooth/l2cap_core.c
>> +++ b/net/bluetooth/l2cap_core.c
>> @@ -233,6 +233,125 @@ static inline void l2cap_chan_set_err(struct l2cap_chan *chan, int err)
>>  	release_sock(sk);
>>  }
>>
>> +/* ---- L2CAP sequence number lists ---- */
>> +
>> +/* For ERTM, ordered lists of sequence numbers must be tracked for
>> + * SREJ requests that are received and for frames that are to be
>> + * retransmitted. These seq_list functions implement a singly-linked
>> + * list in an array, where membership in the list can also be checked
>> + * in constant time. Items can also be added to the tail of the list
>> + * and removed from the head in constant time, without further memory
>> + * allocs or frees.
>> + */
>> +
>> +static int l2cap_seq_list_init(struct l2cap_seq_list *seq_list, u16 size)
>> +{
>> +	u16 alloc_size = 1;
>> +	int i;
>> +
>> +	/* Allocated size is a power of 2 to map sequence numbers
>> +	 * (which may be up to 14 bits) in to a smaller array that is
>> +	 * sized for the negotiated ERTM transmit windows.
>> +	 */
>> +	while (alloc_size && alloc_size <= size)
>> +		alloc_size <<= 1;
>> +	if (!alloc_size)
>> +		return -ENOMEM;
>> +
>
> Is it intended that if size is already equal to power of two you still double it?
> And maybe use roundup_pow_of_two macro here?

I didn't know about roundup_pow_of_two, that would be good to use -- 
and it would address the potential overallocation you noticed.

>> +	seq_list->list = kzalloc(sizeof(u16) * alloc_size, GFP_KERNEL);
>> +	if (!seq_list->list)
>> +		return -ENOMEM;
>> +
>> +	seq_list->mask = alloc_size - 1;
>> +	seq_list->head = L2CAP_SEQ_LIST_CLEAR;
>> +	seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
>> +	for (i = 0; i < alloc_size; i++)
>> +		seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
>
> Could use memset for this instead of loop, and maybe use kcalloc instead of
> kzalloc to allocate array?

L2CAP_SEQ_LIST_CLEAR is 0xffff, not 0, so it seems best to change the 
kzalloc to kmalloc.

It is a coincidence that L2CAP_SEQ_LIST_CLEAR has identical upper and 
lower bytes so memset would work, but I think it's better to keep the 
existing code for readability.  This function is not called often, and 
not in performance-critical places.

>> +
>> +	return 0;
>> +}
>> +
>> +static inline void l2cap_seq_list_free(struct l2cap_seq_list *seq_list)
>> +{
>> +	kfree(seq_list->list);
>> +}
>> +
>> +static inline bool l2cap_seq_list_contains(struct l2cap_seq_list *seq_list,
>> +					   u16 seq)
>> +{
>> +	/* Constant-time check for list membership */
>> +	return seq_list->list[seq & seq_list->mask] != L2CAP_SEQ_LIST_CLEAR;
>> +}
>> +
>> +static u16 l2cap_seq_list_remove(struct l2cap_seq_list *seq_list, u16 seq)
>> +{
>> +	u16 mask = seq_list->mask;
>> +
>> +	if (seq_list->head == L2CAP_SEQ_LIST_CLEAR) {
>> +		/* In case someone tries to pop the head of an empty list */
>> +		return L2CAP_SEQ_LIST_CLEAR;
>> +	} else if (seq_list->head == seq) {
>> +		/* Head can be removed in constant time */
>> +		seq_list->head = seq_list->list[seq & mask];
>> +		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
>> +
>> +		if (seq_list->head == L2CAP_SEQ_LIST_TAIL) {
>> +			seq_list->head = L2CAP_SEQ_LIST_CLEAR;
>> +			seq_list->tail = L2CAP_SEQ_LIST_CLEAR;
>> +		}
>> +	} else {
>> +		/* Walk the list to find the sequence number */
>> +		u16 prev = seq_list->head;
>> +		while (seq_list->list[prev & mask] != seq) {
>> +			prev = seq_list->list[prev & mask];
>> +			if (prev == L2CAP_SEQ_LIST_TAIL)
>> +				return L2CAP_SEQ_LIST_CLEAR;
>> +		}
>> +
>> +		/* Unlink the number from the list and clear it */
>> +		seq_list->list[prev & mask] = seq_list->list[seq & mask];
>> +		seq_list->list[seq & mask] = L2CAP_SEQ_LIST_CLEAR;
>> +		if (seq_list->tail == seq)
>> +			seq_list->tail = prev;
>> +	}
>> +	return seq;
>> +}
>> +
>> +static u16 l2cap_seq_list_pop(struct l2cap_seq_list *seq_list)
>> +{
>> +	/* Remove the head in constant time */
>> +	return l2cap_seq_list_remove(seq_list, seq_list->head);
>> +}
>> +
>> +static void l2cap_seq_list_clear(struct l2cap_seq_list *seq_list)
>> +{
>> +	if (seq_list->head != L2CAP_SEQ_LIST_CLEAR) {
>> +		u16 i;
>> +		for (i = 0; i <= seq_list->mask; i++)
>> +			seq_list->list[i] = L2CAP_SEQ_LIST_CLEAR;
>
> maybe use memset?
(see above)

Thanks for your comments,

--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum