This is the first of several patch series to rework the ERTM state
machine. v1 of this patch set had two patches updating header files
that were already merged, v2 has some reworked utility functions that
are used by the new state machine.
Mat Martineau (2):
Bluetooth: Add the l2cap_seq_list structure for tracking frames
Bluetooth: Functions parsing or generating ERTM control fields
include/net/bluetooth/l2cap.h | 12 +++
net/bluetooth/l2cap_core.c | 240 +++++++++++++++++++++++++++++++++++++++++
2 files changed, 252 insertions(+)
--
1.7.9.4
--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum
Hi Mat,
On Thu, Mar 29, 2012 at 05:32:49PM -0700, Mat Martineau wrote:
> These functions encode or decode ERTM control fields (extended or
> enhanced) to or from the new l2cap_control structure.
>
> Signed-off-by: Mat Martineau <[email protected]>
> ---
> net/bluetooth/l2cap_core.c | 108 ++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 108 insertions(+)
>
> diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
> index 2414ddd..8905386 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -789,6 +789,106 @@ 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 enhanced,
> + struct l2cap_ctrl *control)
> +{
> + control->reqseq = (enhanced & L2CAP_CTRL_REQSEQ) >>
> + L2CAP_CTRL_REQSEQ_SHIFT;
> + control->final = (enhanced & L2CAP_CTRL_FINAL) >>
> + L2CAP_CTRL_FINAL_SHIFT;
> +
> + if (enhanced & L2CAP_CTRL_FRAME_TYPE) {
> + /* S-Frame */
> + control->sframe = 1;
> + control->poll = (enhanced & L2CAP_CTRL_POLL) >>
> + L2CAP_CTRL_POLL_SHIFT;
> + control->super = (enhanced & L2CAP_CTRL_SUPERVISE) >>
> + L2CAP_CTRL_SUPER_SHIFT;
> +
> + control->sar = 0;
> + control->txseq = 0;
> + } else {
> + /* I-Frame */
> + control->sframe = 0;
> + control->sar = (enhanced & L2CAP_CTRL_SAR) >>
> + L2CAP_CTRL_SAR_SHIFT;
> + control->txseq = (enhanced & 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 extended,
> + struct l2cap_ctrl *control)
> +{
> + control->reqseq = (extended & L2CAP_EXT_CTRL_REQSEQ) >>
> + L2CAP_EXT_CTRL_REQSEQ_SHIFT;
> + control->final = (extended & L2CAP_EXT_CTRL_FINAL) >>
> + L2CAP_EXT_CTRL_FINAL_SHIFT;
> +
> + if (extended & L2CAP_EXT_CTRL_FRAME_TYPE) {
> + /* S-Frame */
> + control->sframe = 1;
> + control->poll = (extended & L2CAP_EXT_CTRL_POLL) >>
> + L2CAP_EXT_CTRL_POLL_SHIFT;
> + control->super = (extended & L2CAP_EXT_CTRL_SUPERVISE) >>
> + L2CAP_EXT_CTRL_SUPER_SHIFT;
> +
> + control->sar = 0;
> + control->txseq = 0;
> + } else {
> + /* I-Frame */
> + control->sframe = 0;
> + control->sar = (extended & L2CAP_EXT_CTRL_SAR) >>
> + L2CAP_EXT_CTRL_SAR_SHIFT;
> + control->txseq = (extended & L2CAP_EXT_CTRL_TXSEQ) >>
> + L2CAP_EXT_CTRL_TXSEQ_SHIFT;
> +
> + control->poll = 0;
> + control->super = 0;
> + }
> +}
> +
> static inline int __l2cap_no_conn_pending(struct l2cap_chan *chan)
> {
> return !test_bit(CONF_CONNECT_PEND, &chan->conf_state);
> @@ -4350,6 +4450,14 @@ 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;
>
> + 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);
> + }
> +
Here I would change it to function, something like: __set_control(chan, skb);
Otherwise looks good.
Best regards
Andrei Emeltchenko
> control = __get_control(chan, skb->data);
> skb_pull(skb, __ctrl_size(chan));
> len = skb->len;
> --
Hi Mat,
On Thu, Mar 29, 2012 at 05:32:48PM -0700, Mat Martineau wrote:
> 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 <[email protected]>
> ---
> include/net/bluetooth/l2cap.h | 12 ++++
> net/bluetooth/l2cap_core.c | 132 +++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 144 insertions(+)
>
> 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..2414ddd 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -233,6 +233,134 @@ 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 err = 0;
> + 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 err;
return 0; err is not used and shall be removed.
Otherwise looks good.
Best regards
Andrei Emeltchenko
Hi Mat,
> These functions encode or decode ERTM control fields (extended or
> enhanced) to or from the new l2cap_control structure.
>
> Signed-off-by: Mat Martineau <[email protected]>
> ---
> net/bluetooth/l2cap_core.c | 108 ++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 108 insertions(+)
>
> diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
> index 2414ddd..8905386 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -789,6 +789,106 @@ 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 enhanced,
> + struct l2cap_ctrl *control)
> +{
> + control->reqseq = (enhanced & L2CAP_CTRL_REQSEQ) >>
> + L2CAP_CTRL_REQSEQ_SHIFT;
> + control->final = (enhanced & L2CAP_CTRL_FINAL) >>
> + L2CAP_CTRL_FINAL_SHIFT;
> +
> + if (enhanced & L2CAP_CTRL_FRAME_TYPE) {
> + /* S-Frame */
> + control->sframe = 1;
> + control->poll = (enhanced & L2CAP_CTRL_POLL) >>
> + L2CAP_CTRL_POLL_SHIFT;
> + control->super = (enhanced & L2CAP_CTRL_SUPERVISE) >>
> + L2CAP_CTRL_SUPER_SHIFT;
these look wrong to me from a coding style point of view. I think we
either ignore the 80 character rule here. Or we use a define that does
this for us. Something like this:
#define __get_poll(e) (((e) & L2CAP_CTRL_POLL) >> L2CAP_CTRL_POLL_SHIFT)
> +
> + control->sar = 0;
> + control->txseq = 0;
> + } else {
> + /* I-Frame */
> + control->sframe = 0;
> + control->sar = (enhanced & L2CAP_CTRL_SAR) >>
> + L2CAP_CTRL_SAR_SHIFT;
> + control->txseq = (enhanced & L2CAP_CTRL_TXSEQ) >>
> + L2CAP_CTRL_TXSEQ_SHIFT;
Or maybe even something funky like this:
#define __get_ctrl(e, f) (((e) & f) >> (f ## _SHIFT))
And then you could just use it like this:
control->sar = __get_ctrl(enhanced, L2CAP_CTRL_SAR);
Or something similar. I am just throwing ideas into the room.
Regards
Marcel
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 <[email protected]>
> ---
> include/net/bluetooth/l2cap.h | 12 ++++
> net/bluetooth/l2cap_core.c | 132 +++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 144 insertions(+)
>
> 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..2414ddd 100644
> --- a/net/bluetooth/l2cap_core.c
> +++ b/net/bluetooth/l2cap_core.c
> @@ -233,6 +233,134 @@ 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 err = 0;
> + 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 err;
> +}
> +
> +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;
> +
> + BT_DBG("seq_list %p, seq %d", seq_list, (int) seq);
> +
> + if (seq_list->head == L2CAP_SEQ_LIST_CLEAR) {
> + /* In case someone tries to pop the head of an empty list */
> + BT_DBG("List empty");
I think that see debug statement should go away. Do you really need
them?
> + return L2CAP_SEQ_LIST_CLEAR;
> + } else if (seq_list->head == seq) {
> + /* Head can be removed in constant time */
> + BT_DBG("Remove head");
> + 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;
> + BT_DBG("Find and remove");
> + while (seq_list->list[prev & mask] != seq) {
> + prev = seq_list->list[prev & mask];
> + if (prev == L2CAP_SEQ_LIST_TAIL) {
> + BT_DBG("seq %d not in list", (int) seq);
> + 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 */
> + BT_DBG("seq_list %p, seq %d", seq_list, (int) seq);
> +
> + 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 +532,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);
> @@ -2052,6 +2182,8 @@ static inline void l2cap_ertm_init(struct l2cap_chan *chan)
>
> skb_queue_head_init(&chan->srej_q);
>
> + l2cap_seq_list_init(&chan->srej_list, chan->tx_win);
> + l2cap_seq_list_init(&chan->retrans_list, chan->remote_tx_win);
> INIT_LIST_HEAD(&chan->srej_l);
> }
>
Besides removing the debug statements, this looks good to me.
Acked-by: Marcel Holtmann <[email protected]>
Regards
Marcel
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 <[email protected]>
---
include/net/bluetooth/l2cap.h | 12 ++++
net/bluetooth/l2cap_core.c | 132 +++++++++++++++++++++++++++++++++++++++++
2 files changed, 144 insertions(+)
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..2414ddd 100644
--- a/net/bluetooth/l2cap_core.c
+++ b/net/bluetooth/l2cap_core.c
@@ -233,6 +233,134 @@ 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 err = 0;
+ 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 err;
+}
+
+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;
+
+ BT_DBG("seq_list %p, seq %d", seq_list, (int) seq);
+
+ if (seq_list->head == L2CAP_SEQ_LIST_CLEAR) {
+ /* In case someone tries to pop the head of an empty list */
+ BT_DBG("List empty");
+ return L2CAP_SEQ_LIST_CLEAR;
+ } else if (seq_list->head == seq) {
+ /* Head can be removed in constant time */
+ BT_DBG("Remove head");
+ 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;
+ BT_DBG("Find and remove");
+ while (seq_list->list[prev & mask] != seq) {
+ prev = seq_list->list[prev & mask];
+ if (prev == L2CAP_SEQ_LIST_TAIL) {
+ BT_DBG("seq %d not in list", (int) seq);
+ 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 */
+ BT_DBG("seq_list %p, seq %d", seq_list, (int) seq);
+
+ 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 +532,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);
@@ -2052,6 +2182,8 @@ static inline void l2cap_ertm_init(struct l2cap_chan *chan)
skb_queue_head_init(&chan->srej_q);
+ l2cap_seq_list_init(&chan->srej_list, chan->tx_win);
+ l2cap_seq_list_init(&chan->retrans_list, chan->remote_tx_win);
INIT_LIST_HEAD(&chan->srej_l);
}
--
1.7.9.4
--
Mat Martineau
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum
These functions encode or decode ERTM control fields (extended or
enhanced) to or from the new l2cap_control structure.
Signed-off-by: Mat Martineau <[email protected]>
---
net/bluetooth/l2cap_core.c | 108 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 108 insertions(+)
diff --git a/net/bluetooth/l2cap_core.c b/net/bluetooth/l2cap_core.c
index 2414ddd..8905386 100644
--- a/net/bluetooth/l2cap_core.c
+++ b/net/bluetooth/l2cap_core.c
@@ -789,6 +789,106 @@ 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 enhanced,
+ struct l2cap_ctrl *control)
+{
+ control->reqseq = (enhanced & L2CAP_CTRL_REQSEQ) >>
+ L2CAP_CTRL_REQSEQ_SHIFT;
+ control->final = (enhanced & L2CAP_CTRL_FINAL) >>
+ L2CAP_CTRL_FINAL_SHIFT;
+
+ if (enhanced & L2CAP_CTRL_FRAME_TYPE) {
+ /* S-Frame */
+ control->sframe = 1;
+ control->poll = (enhanced & L2CAP_CTRL_POLL) >>
+ L2CAP_CTRL_POLL_SHIFT;
+ control->super = (enhanced & L2CAP_CTRL_SUPERVISE) >>
+ L2CAP_CTRL_SUPER_SHIFT;
+
+ control->sar = 0;
+ control->txseq = 0;
+ } else {
+ /* I-Frame */
+ control->sframe = 0;
+ control->sar = (enhanced & L2CAP_CTRL_SAR) >>
+ L2CAP_CTRL_SAR_SHIFT;
+ control->txseq = (enhanced & 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 extended,
+ struct l2cap_ctrl *control)
+{
+ control->reqseq = (extended & L2CAP_EXT_CTRL_REQSEQ) >>
+ L2CAP_EXT_CTRL_REQSEQ_SHIFT;
+ control->final = (extended & L2CAP_EXT_CTRL_FINAL) >>
+ L2CAP_EXT_CTRL_FINAL_SHIFT;
+
+ if (extended & L2CAP_EXT_CTRL_FRAME_TYPE) {
+ /* S-Frame */
+ control->sframe = 1;
+ control->poll = (extended & L2CAP_EXT_CTRL_POLL) >>
+ L2CAP_EXT_CTRL_POLL_SHIFT;
+ control->super = (extended & L2CAP_EXT_CTRL_SUPERVISE) >>
+ L2CAP_EXT_CTRL_SUPER_SHIFT;
+
+ control->sar = 0;
+ control->txseq = 0;
+ } else {
+ /* I-Frame */
+ control->sframe = 0;
+ control->sar = (extended & L2CAP_EXT_CTRL_SAR) >>
+ L2CAP_EXT_CTRL_SAR_SHIFT;
+ control->txseq = (extended & L2CAP_EXT_CTRL_TXSEQ) >>
+ L2CAP_EXT_CTRL_TXSEQ_SHIFT;
+
+ control->poll = 0;
+ control->super = 0;
+ }
+}
+
static inline int __l2cap_no_conn_pending(struct l2cap_chan *chan)
{
return !test_bit(CONF_CONNECT_PEND, &chan->conf_state);
@@ -4350,6 +4450,14 @@ 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;
+ 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);
+ }
+
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