[PATCH RFC v2 0/2] can: join filters with per-CPU variables

[PATCH RFC v2 0/2] can: join filters with per-CPU variables

[Oliver Hartkopp]

Hi all,

as Andre Naujoks found some problems in my first patches with multi-threading
I did some investigation how to handle variables to be written inside the
NET_RX softirq without locking. As far as I was able to test this code it works
properly now - even with the multi-thread test from Andre.

If you know how to use per-CPU variables inside NET_RX softirq I would appreciate
your review as I'm not that sure that the per-CPU code is correct. It's my first
time using this technique and is only what I was able to get from other code
examples and available kernel docs.

Many thanks,
Oliver

Oliver Hartkopp (2):
  can: fix multiple delivery of a single CAN frame for overlapping CAN filters
  can: introduce new raw socket option to join the given CAN filters

 Documentation/networking/can.txt | 20 +++++++++++--
 include/uapi/linux/can/raw.h     |  1 +
 net/can/raw.c                    | 64 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 83 insertions(+), 2 deletions(-)

-- 
2.1.4

[PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

The CAN_RAW socket can set multiple CAN identifier specific filters that lead
to multiple filters in the af_can.c filter processing. These filters are
indenpendent from each other which leads to logical OR'ed filters when applied.

This patch makes sure that every CAN frame which is filtered for a specific
socket is only delivered once to the user space. This is independent from the
number of matching CAN filters of this socket.

As the can_raw() function is executed from NET_RX softirq the introduced
variables are implemented as per-CPU variables to avoid extensive locking at
CAN frame reception time.

Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
---
 net/can/raw.c | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/net/can/raw.c b/net/can/raw.c
index 00c13ef..866a9b3 100644
--- a/net/can/raw.c
+++ b/net/can/raw.c
@@ -86,6 +86,8 @@ struct raw_sock {
 	struct can_filter dfilter; /* default/single filter */
 	struct can_filter *filter; /* pointer to filter(s) */
 	can_err_mask_t err_mask;
+	struct sk_buff __percpu **uniq_skb;
+	ktime_t __percpu *uniq_tstamp;
 };
 
 /*
@@ -123,6 +125,15 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
 	if (!ro->fd_frames && oskb->len != CAN_MTU)
 		return;
 
+	/* eliminate multiple filter matches for the same skb */
+	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
+	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
+			return;
+	} else {
+		*this_cpu_ptr(ro->uniq_skb) = oskb;
+		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
+	}
+
 	/* clone the given skb to be able to enqueue it into the rcv queue */
 	skb = skb_clone(oskb, GFP_ATOMIC);
 	if (!skb)
@@ -282,6 +293,7 @@ static int raw_notifier(struct notifier_block *nb,
 static int raw_init(struct sock *sk)
 {
 	struct raw_sock *ro = raw_sk(sk);
+	int cpu;
 
 	ro->bound            = 0;
 	ro->ifindex          = 0;
@@ -297,6 +309,20 @@ static int raw_init(struct sock *sk)
 	ro->recv_own_msgs    = 0;
 	ro->fd_frames        = 0;
 
+	ro->uniq_skb = alloc_percpu(struct sk_buff *);
+	if (unlikely(ro->uniq_skb == NULL))
+		return -ENOMEM;
+	for_each_possible_cpu(cpu)
+		*per_cpu_ptr(ro->uniq_skb, cpu) = NULL;
+
+	ro->uniq_tstamp = alloc_percpu(ktime_t);
+	if (unlikely(ro->uniq_tstamp == NULL)) {
+		free_percpu(ro->uniq_skb);
+		return -ENOMEM;
+	}
+	for_each_possible_cpu(cpu)
+		*per_cpu_ptr(ro->uniq_tstamp, cpu) = ktime_set(0, 0);
+
 	/* set notifier */
 	ro->notifier.notifier_call = raw_notifier;
 
@@ -339,6 +365,8 @@ static int raw_release(struct socket *sock)
 	ro->ifindex = 0;
 	ro->bound   = 0;
 	ro->count   = 0;
+	free_percpu(ro->uniq_skb);
+	free_percpu(ro->uniq_tstamp);
 
 	sock_orphan(sk);
 	sock->sk = NULL;
-- 
2.1.4

[PATCH RFC v2 2/2] can: introduce new raw socket option to join the given CAN filters

[Oliver Hartkopp]

The CAN_RAW socket can set multiple CAN identifier specific filters that lead
to multiple filters in the af_can.c filter processing. These filters are
indenpendent from each other which leads to logical OR'ed filters when applied.

This socket option joines the given CAN filters in the way that only CAN frames
are passed to user space that matched *all* given CAN filters. The semantic for
the applied filters is therefore changed to a logical AND.

This is useful especially when the filterset is a combination of filters where
the CAN_INV_FILTER flag is set in order to notch single CAN IDs or CAN ID
ranges from the incoming traffic.

As the can_raw() function is executed from NET_RX softirq the introduced
variables are implemented as per-CPU variables to avoid extensive locking at
CAN frame reception time.

Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
---
 Documentation/networking/can.txt | 20 ++++++++++++++++++--
 include/uapi/linux/can/raw.h     |  1 +
 net/can/raw.c                    | 36 ++++++++++++++++++++++++++++++++++++
 3 files changed, 55 insertions(+), 2 deletions(-)

diff --git a/Documentation/networking/can.txt b/Documentation/networking/can.txt
index 0a2859a..5abad1e 100644
--- a/Documentation/networking/can.txt
+++ b/Documentation/networking/can.txt
@@ -22,7 +22,8 @@ This file contains
       4.1.3 RAW socket option CAN_RAW_LOOPBACK
       4.1.4 RAW socket option CAN_RAW_RECV_OWN_MSGS
       4.1.5 RAW socket option CAN_RAW_FD_FRAMES
-      4.1.6 RAW socket returned message flags
+      4.1.6 RAW socket option CAN_RAW_JOIN_FILTERS
+      4.1.7 RAW socket returned message flags
     4.2 Broadcast Manager protocol sockets (SOCK_DGRAM)
       4.2.1 Broadcast Manager operations
       4.2.2 Broadcast Manager message flags
@@ -601,7 +602,22 @@ solution for a couple of reasons:
   CAN FD frames by checking if the device maximum transfer unit is CANFD_MTU.
   The CAN device MTU can be retrieved e.g. with a SIOCGIFMTU ioctl() syscall.
 
-  4.1.6 RAW socket returned message flags
+  4.1.6 RAW socket option CAN_RAW_JOIN_FILTERS
+
+  The CAN_RAW socket can set multiple CAN identifier specific filters that
+  lead to multiple filters in the af_can.c filter processing. These filters
+  are indenpendent from each other which leads to logical OR'ed filters when
+  applied (see 4.1.1).
+
+  This socket option joines the given CAN filters in the way that only CAN
+  frames are passed to user space that matched *all* given CAN filters. The
+  semantic for the applied filters is therefore changed to a logical AND.
+
+  This is useful especially when the filterset is a combination of filters
+  where the CAN_INV_FILTER flag is set in order to notch single CAN IDs or
+  CAN ID ranges from the incoming traffic.
+
+  4.1.7 RAW socket returned message flags
 
   When using recvmsg() call, the msg->msg_flags may contain following flags:
 
diff --git a/include/uapi/linux/can/raw.h b/include/uapi/linux/can/raw.h
index 78ec76f..8735f108 100644
--- a/include/uapi/linux/can/raw.h
+++ b/include/uapi/linux/can/raw.h
@@ -57,6 +57,7 @@ enum {
 	CAN_RAW_LOOPBACK,	/* local loopback (default:on)       */
 	CAN_RAW_RECV_OWN_MSGS,	/* receive my own msgs (default:off) */
 	CAN_RAW_FD_FRAMES,	/* allow CAN FD frames (default:off) */
+	CAN_RAW_JOIN_FILTERS,	/* all filters must match to trigger */
 };
 
 #endif /* !_UAPI_CAN_RAW_H */
diff --git a/net/can/raw.c b/net/can/raw.c
index 866a9b3..dc68fa0 100644
--- a/net/can/raw.c
+++ b/net/can/raw.c
@@ -82,6 +82,8 @@ struct raw_sock {
 	int loopback;
 	int recv_own_msgs;
 	int fd_frames;
+	int join_filters;
+	int __percpu *join_rx_count;
 	int count;                 /* number of active filters */
 	struct can_filter dfilter; /* default/single filter */
 	struct can_filter *filter; /* pointer to filter(s) */
@@ -128,10 +130,20 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
 	/* eliminate multiple filter matches for the same skb */
 	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
 	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
+		if (ro->join_filters) {
+			this_cpu_inc(*ro->join_rx_count);
+			/* drop frame until all enabled filters matched */
+			if (*this_cpu_ptr(ro->join_rx_count) < ro->count)
+				return;
+		} else
 			return;
 	} else {
 		*this_cpu_ptr(ro->uniq_skb) = oskb;
 		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
+		*this_cpu_ptr(ro->join_rx_count) = 1;
+		/* drop first frame to check all enabled filters? */
+		if (ro->join_filters && ro->count > 1)
+			return;
 	}
 
 	/* clone the given skb to be able to enqueue it into the rcv queue */
@@ -308,6 +320,7 @@ static int raw_init(struct sock *sk)
 	ro->loopback         = 1;
 	ro->recv_own_msgs    = 0;
 	ro->fd_frames        = 0;
+	ro->join_filters     = 0;
 
 	ro->uniq_skb = alloc_percpu(struct sk_buff *);
 	if (unlikely(ro->uniq_skb == NULL))
@@ -323,6 +336,13 @@ static int raw_init(struct sock *sk)
 	for_each_possible_cpu(cpu)
 		*per_cpu_ptr(ro->uniq_tstamp, cpu) = ktime_set(0, 0);
 
+	ro->join_rx_count = alloc_percpu(int);
+	if (unlikely(ro->join_rx_count == NULL)) {
+		free_percpu(ro->uniq_skb);
+		free_percpu(ro->uniq_tstamp);
+		return -ENOMEM;
+	}
+
 	/* set notifier */
 	ro->notifier.notifier_call = raw_notifier;
 
@@ -367,6 +387,7 @@ static int raw_release(struct socket *sock)
 	ro->count   = 0;
 	free_percpu(ro->uniq_skb);
 	free_percpu(ro->uniq_tstamp);
+	free_percpu(ro->join_rx_count);
 
 	sock_orphan(sk);
 	sock->sk = NULL;
@@ -611,6 +632,15 @@ static int raw_setsockopt(struct socket *sock, int level, int optname,
 
 		break;
 
+	case CAN_RAW_JOIN_FILTERS:
+		if (optlen != sizeof(ro->join_filters))
+			return -EINVAL;
+
+		if (copy_from_user(&ro->join_filters, optval, optlen))
+			return -EFAULT;
+
+		break;
+
 	default:
 		return -ENOPROTOOPT;
 	}
@@ -675,6 +705,12 @@ static int raw_getsockopt(struct socket *sock, int level, int optname,
 		val = &ro->fd_frames;
 		break;
 
+	case CAN_RAW_JOIN_FILTERS:
+		if (len > sizeof(int))
+			len = sizeof(int);
+		val = &ro->join_filters;
+		break;
+
 	default:
 		return -ENOPROTOOPT;
 	}
-- 
2.1.4

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 1645 bytes --]

On 03/29/2015 08:09 PM, Oliver Hartkopp wrote:
> The CAN_RAW socket can set multiple CAN identifier specific filters that lead
> to multiple filters in the af_can.c filter processing. These filters are
> indenpendent from each other which leads to logical OR'ed filters when applied.
> 
> This patch makes sure that every CAN frame which is filtered for a specific
> socket is only delivered once to the user space. This is independent from the
> number of matching CAN filters of this socket.
> 
> As the can_raw() function is executed from NET_RX softirq the introduced
> variables are implemented as per-CPU variables to avoid extensive locking at
> CAN frame reception time.
> 
> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
> ---
>  net/can/raw.c | 28 ++++++++++++++++++++++++++++
>  1 file changed, 28 insertions(+)
> 
> diff --git a/net/can/raw.c b/net/can/raw.c
> index 00c13ef..866a9b3 100644
> --- a/net/can/raw.c
> +++ b/net/can/raw.c
> @@ -86,6 +86,8 @@ struct raw_sock {
>  	struct can_filter dfilter; /* default/single filter */
>  	struct can_filter *filter; /* pointer to filter(s) */
>  	can_err_mask_t err_mask;
> +	struct sk_buff __percpu **uniq_skb;
> +	ktime_t __percpu *uniq_tstamp;

What about creating a struct to hold the ktime_t and the skb? BTW: the
pointer to the skb can be marked as const.

Marc
-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 2337 bytes --]

On 03/29/2015 08:09 PM, Oliver Hartkopp wrote:
> The CAN_RAW socket can set multiple CAN identifier specific filters that lead
> to multiple filters in the af_can.c filter processing. These filters are
> indenpendent from each other which leads to logical OR'ed filters when applied.
> 
> This patch makes sure that every CAN frame which is filtered for a specific
> socket is only delivered once to the user space. This is independent from the
> number of matching CAN filters of this socket.
> 
> As the can_raw() function is executed from NET_RX softirq the introduced
> variables are implemented as per-CPU variables to avoid extensive locking at
> CAN frame reception time.
> 
> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
> ---
>  net/can/raw.c | 28 ++++++++++++++++++++++++++++
>  1 file changed, 28 insertions(+)
> 
> diff --git a/net/can/raw.c b/net/can/raw.c
> index 00c13ef..866a9b3 100644
> --- a/net/can/raw.c
> +++ b/net/can/raw.c
> @@ -86,6 +86,8 @@ struct raw_sock {
>  	struct can_filter dfilter; /* default/single filter */
>  	struct can_filter *filter; /* pointer to filter(s) */
>  	can_err_mask_t err_mask;
> +	struct sk_buff __percpu **uniq_skb;
> +	ktime_t __percpu *uniq_tstamp;
>  };
>  
>  /*
> @@ -123,6 +125,15 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
>  	if (!ro->fd_frames && oskb->len != CAN_MTU)
>  		return;
>  
> +	/* eliminate multiple filter matches for the same skb */
> +	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
> +	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
> +			return;
> +	} else {
> +		*this_cpu_ptr(ro->uniq_skb) = oskb;
> +		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
> +	}
> +

What happens if you're preempted somewhere in this code, it's not
atomic? I think, if we only have to take care about the skb, an atomic
compare exchange would work. But we have two variables....If you use a
struct (see previous mail), I think the usage of get_cpu_ptr(),
git_cpu_ptr() ensures that we're not preempted.

Marc

-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 1820 bytes --]

On 03/30/2015 12:10 PM, Marc Kleine-Budde wrote:
> On 03/29/2015 08:09 PM, Oliver Hartkopp wrote:
>> The CAN_RAW socket can set multiple CAN identifier specific filters that lead
>> to multiple filters in the af_can.c filter processing. These filters are
>> indenpendent from each other which leads to logical OR'ed filters when applied.
       ^
independent

>> This patch makes sure that every CAN frame which is filtered for a specific
>> socket is only delivered once to the user space. This is independent from the
>> number of matching CAN filters of this socket.
>>
>> As the can_raw() function is executed from NET_RX softirq the introduced
>> variables are implemented as per-CPU variables to avoid extensive locking at
>> CAN frame reception time.
>>
>> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>

>> +	/* eliminate multiple filter matches for the same skb */
>> +	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>> +	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>> +			return;
>> +	} else {
>> +		*this_cpu_ptr(ro->uniq_skb) = oskb;
>> +		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
>> +	}
>> +
> 
> What happens if you're preempted somewhere in this code, it's not
> atomic? I think, if we only have to take care about the skb, an atomic
> compare exchange would work. But we have two variables....If you use a
> struct (see previous mail), I think the usage of get_cpu_ptr(),
> git_cpu_ptr() ensures that we're not preempted.
  ^^^^^^^^^^^^^
put_cpu_ptr()

Marc

-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

On 30.03.2015 11:50, Marc Kleine-Budde wrote:

>>   	can_err_mask_t err_mask;
>> +	struct sk_buff __percpu **uniq_skb;
>> +	ktime_t __percpu *uniq_tstamp;
>
> What about creating a struct to hold the ktime_t and the skb? BTW: the
> pointer to the skb can be marked as const.

Don't think so.

The pointer points to some allocated memory.

Regards,
Oliver

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 831 bytes --]

On 03/30/2015 12:29 PM, Oliver Hartkopp wrote:
> On 30.03.2015 11:50, Marc Kleine-Budde wrote:
> 
>>>   	can_err_mask_t err_mask;
>>> +	struct sk_buff __percpu **uniq_skb;
>>> +	ktime_t __percpu *uniq_tstamp;
>>
>> What about creating a struct to hold the ktime_t and the skb? BTW: the
>> pointer to the skb can be marked as const.
> 
> Don't think so.
> 
> The pointer points to some allocated memory.

Yes, but the allocated memory points to a skb which is not modified, so
it's a:

struct sk_buff __percpu * const *uniq_skb;

Marc

-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

On 30.03.2015 12:10, Marc Kleine-Budde wrote:

>>
>> +	/* eliminate multiple filter matches for the same skb */
>> +	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>> +	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>> +			return;
>> +	} else {
>> +		*this_cpu_ptr(ro->uniq_skb) = oskb;
>> +		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
>> +	}
>> +
>
> What happens if you're preempted somewhere in this code, it's not
> atomic? I think, if we only have to take care about the skb, an atomic
> compare exchange would work. But we have two variables....If you use a
> struct (see previous mail), I think the usage of get_cpu_ptr(),
> git_cpu_ptr() ensures that we're not preempted.
>

Please check out

https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/

And especially 
https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/x173.html#LOCK-SOFTIRQS-SAME

When a softirq processes an incoming skb this remains on that selected CPU.

The mutithread-test from Andre just lead to the problem that the (former 
single instance) variables ro->uniq_skb and ro->uniq_tstamp have been used by 
different CPUs which made the checks unreliable.

So following the documentation and other examples in kernel source you can

- use spinlocks in can_receive() in af_can.c (instead of rcu_read_lock())
- use per-CPU variables to allow the softirq to run in parallel

Just make the variables atomic (as you suggested) is as bad as introduce 
spinlocks in can_receive() as you reduce the skb processing to just one 
thread. So at least percpu is the best for performance but needs to create a 
vector of variables (percpu).

Putting a struct into these percpu handling can be done - but does it increase 
the readability in this case?

Regards,
Oliver

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Sergei Shtylyov]

Hello.

On 3/29/2015 9:09 PM, Oliver Hartkopp wrote:

> The CAN_RAW socket can set multiple CAN identifier specific filters that lead
> to multiple filters in the af_can.c filter processing. These filters are
> indenpendent from each other which leads to logical OR'ed filters when applied.

> This patch makes sure that every CAN frame which is filtered for a specific
> socket is only delivered once to the user space. This is independent from the
> number of matching CAN filters of this socket.

> As the can_raw() function is executed from NET_RX softirq the introduced
> variables are implemented as per-CPU variables to avoid extensive locking at
> CAN frame reception time.

> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
> ---
>   net/can/raw.c | 28 ++++++++++++++++++++++++++++
>   1 file changed, 28 insertions(+)

> diff --git a/net/can/raw.c b/net/can/raw.c
> index 00c13ef..866a9b3 100644
> --- a/net/can/raw.c
> +++ b/net/can/raw.c
[...]
> @@ -123,6 +125,15 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
>   	if (!ro->fd_frames && oskb->len != CAN_MTU)
>   		return;
>
> +	/* eliminate multiple filter matches for the same skb */
> +	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
> +	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
> +			return;

    Over-indented.

> +	} else {
> +		*this_cpu_ptr(ro->uniq_skb) = oskb;
> +		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
> +	}
> +
>   	/* clone the given skb to be able to enqueue it into the rcv queue */
>   	skb = skb_clone(oskb, GFP_ATOMIC);
>   	if (!skb)
[...]
> @@ -297,6 +309,20 @@ static int raw_init(struct sock *sk)
>   	ro->recv_own_msgs    = 0;
>   	ro->fd_frames        = 0;
>
> +	ro->uniq_skb = alloc_percpu(struct sk_buff *);
> +	if (unlikely(ro->uniq_skb == NULL))
> +		return -ENOMEM;
> +	for_each_possible_cpu(cpu)
> +		*per_cpu_ptr(ro->uniq_skb, cpu) = NULL;
> +
> +	ro->uniq_tstamp = alloc_percpu(ktime_t);
> +	if (unlikely(ro->uniq_tstamp == NULL)) {

    !ro->uniq_tstamp is preferred in the networking code.

[...]

WBR, Sergei

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

On 30.03.2015 14:33, Sergei Shtylyov wrote:
> On 3/29/2015 9:09 PM, Oliver Hartkopp wrote:
>>
>> +    /* eliminate multiple filter matches for the same skb */
>> +    if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>> +        ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>> +            return;
>
>     Over-indented.
>

I was asked about that before. AFAIK the *skb is no unique identifier over a 
longer period of time. But together with the timestamp it becomes unique.
Or do you have a better solution to detect identical skbs?

CAN skbs do not have a (rx)hash so far and I wonder if it's worth to compute 
the hash in favor to check the *skb and the timestamp here ...


>> +
>> +    ro->uniq_tstamp = alloc_percpu(ktime_t);
>> +    if (unlikely(ro->uniq_tstamp == NULL)) {
>
>     !ro->uniq_tstamp is preferred in the networking code.
>

Ok. Will change that.

Best regards,
Oliver

> [...]
>
> WBR, Sergei
>

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Sergei Shtylyov]

Hello.

On 03/30/2015 06:49 PM, Oliver Hartkopp wrote:

>>> +    /* eliminate multiple filter matches for the same skb */
>>> +    if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>>> +        ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>>> +            return;

>>     Over-indented.

> I was asked about that before. AFAIK the *skb is no unique identifier over a
> longer period of time. But together with the timestamp it becomes unique.
> Or do you have a better solution to detect identical skbs?

    I just said that *return* was too far to the right, that's all. :-)

> CAN skbs do not have a (rx)hash so far and I wonder if it's worth to compute
> the hash in favor to check the *skb and the timestamp here ...

[...]

> Best regards,
> Oliver

WBR, Sergei

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

On 30.03.2015 19:14, Sergei Shtylyov wrote:
> On 03/30/2015 06:49 PM, Oliver Hartkopp wrote:
>
>>>> +    /* eliminate multiple filter matches for the same skb */
>>>> +    if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>>>> +        ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>>>> +            return;
>
>>>     Over-indented.
>
>> I was asked about that before. AFAIK the *skb is no unique identifier over a
>> longer period of time. But together with the timestamp it becomes unique.
>> Or do you have a better solution to detect identical skbs?
>
>     I just said that *return* was too far to the right, that's all. :-)

Oh, ok ...

I mixed indented with intended %-)

My bad.

Will fix that in v3 too.

Good thing: So far no one complained about the __percpu stuff ...

Many thanks,
Oliver

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 2456 bytes --]

On 03/30/2015 12:41 PM, Oliver Hartkopp wrote:
> On 30.03.2015 12:10, Marc Kleine-Budde wrote:
> 
>>>
>>> +	/* eliminate multiple filter matches for the same skb */
>>> +	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>>> +	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>>> +			return;
>>> +	} else {
>>> +		*this_cpu_ptr(ro->uniq_skb) = oskb;
>>> +		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
>>> +	}
>>> +
>>
>> What happens if you're preempted somewhere in this code, it's not
>> atomic? I think, if we only have to take care about the skb, an atomic
>> compare exchange would work. But we have two variables....If you use a
>> struct (see previous mail), I think the usage of get_cpu_ptr(),
>> git_cpu_ptr() ensures that we're not preempted.
>>
> 
> Please check out
> 
> https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
> 
> And especially 
> https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/x173.html#LOCK-SOFTIRQS-SAME
> 
> When a softirq processes an incoming skb this remains on that selected CPU.

Okay, I was not sure about this. What about preempt_rt?

> The mutithread-test from Andre just lead to the problem that the (former 
> single instance) variables ro->uniq_skb and ro->uniq_tstamp have been used by 
> different CPUs which made the checks unreliable.

> So following the documentation and other examples in kernel source you can
> 
> - use spinlocks in can_receive() in af_can.c (instead of rcu_read_lock())
> - use per-CPU variables to allow the softirq to run in parallel
> 
> Just make the variables atomic (as you suggested) is as bad as introduce 
> spinlocks in can_receive() as you reduce the skb processing to just one 
> thread. So at least percpu is the best for performance but needs to create a 
> vector of variables (percpu).

Ack, lockless atomic-compare-exchange is only possbile for a single
variable.

> Putting a struct into these percpu handling can be done - but does it increase 
> the readability in this case?

It saves ressources, 1 pointer instead of 3 (considering both of your
patches) and only 1 allocation.

Marc

-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 2/2] can: introduce new raw socket option to join the given CAN filters

[Marc Kleine-Budde]

[-- Attachment #1: Type: text/plain, Size: 5429 bytes --]

On 03/29/2015 08:09 PM, Oliver Hartkopp wrote:
> The CAN_RAW socket can set multiple CAN identifier specific filters that lead
> to multiple filters in the af_can.c filter processing. These filters are
> indenpendent from each other which leads to logical OR'ed filters when applied.
> 
> This socket option joines the given CAN filters in the way that only CAN frames
> are passed to user space that matched *all* given CAN filters. The semantic for
> the applied filters is therefore changed to a logical AND.
> 
> This is useful especially when the filterset is a combination of filters where
> the CAN_INV_FILTER flag is set in order to notch single CAN IDs or CAN ID
> ranges from the incoming traffic.
> 
> As the can_raw() function is executed from NET_RX softirq the introduced
> variables are implemented as per-CPU variables to avoid extensive locking at
> CAN frame reception time.
> 
> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
> ---
>  Documentation/networking/can.txt | 20 ++++++++++++++++++--
>  include/uapi/linux/can/raw.h     |  1 +
>  net/can/raw.c                    | 36 ++++++++++++++++++++++++++++++++++++
>  3 files changed, 55 insertions(+), 2 deletions(-)
> 
> diff --git a/Documentation/networking/can.txt b/Documentation/networking/can.txt
> index 0a2859a..5abad1e 100644
> --- a/Documentation/networking/can.txt
> +++ b/Documentation/networking/can.txt
> @@ -22,7 +22,8 @@ This file contains
>        4.1.3 RAW socket option CAN_RAW_LOOPBACK
>        4.1.4 RAW socket option CAN_RAW_RECV_OWN_MSGS
>        4.1.5 RAW socket option CAN_RAW_FD_FRAMES
> -      4.1.6 RAW socket returned message flags
> +      4.1.6 RAW socket option CAN_RAW_JOIN_FILTERS
> +      4.1.7 RAW socket returned message flags
>      4.2 Broadcast Manager protocol sockets (SOCK_DGRAM)
>        4.2.1 Broadcast Manager operations
>        4.2.2 Broadcast Manager message flags
> @@ -601,7 +602,22 @@ solution for a couple of reasons:
>    CAN FD frames by checking if the device maximum transfer unit is CANFD_MTU.
>    The CAN device MTU can be retrieved e.g. with a SIOCGIFMTU ioctl() syscall.
>  
> -  4.1.6 RAW socket returned message flags
> +  4.1.6 RAW socket option CAN_RAW_JOIN_FILTERS
> +
> +  The CAN_RAW socket can set multiple CAN identifier specific filters that
> +  lead to multiple filters in the af_can.c filter processing. These filters
> +  are indenpendent from each other which leads to logical OR'ed filters when
> +  applied (see 4.1.1).
> +
> +  This socket option joines the given CAN filters in the way that only CAN
> +  frames are passed to user space that matched *all* given CAN filters. The
> +  semantic for the applied filters is therefore changed to a logical AND.
> +
> +  This is useful especially when the filterset is a combination of filters
> +  where the CAN_INV_FILTER flag is set in order to notch single CAN IDs or
> +  CAN ID ranges from the incoming traffic.
> +
> +  4.1.7 RAW socket returned message flags
>  
>    When using recvmsg() call, the msg->msg_flags may contain following flags:
>  
> diff --git a/include/uapi/linux/can/raw.h b/include/uapi/linux/can/raw.h
> index 78ec76f..8735f108 100644
> --- a/include/uapi/linux/can/raw.h
> +++ b/include/uapi/linux/can/raw.h
> @@ -57,6 +57,7 @@ enum {
>  	CAN_RAW_LOOPBACK,	/* local loopback (default:on)       */
>  	CAN_RAW_RECV_OWN_MSGS,	/* receive my own msgs (default:off) */
>  	CAN_RAW_FD_FRAMES,	/* allow CAN FD frames (default:off) */
> +	CAN_RAW_JOIN_FILTERS,	/* all filters must match to trigger */
>  };
>  
>  #endif /* !_UAPI_CAN_RAW_H */
> diff --git a/net/can/raw.c b/net/can/raw.c
> index 866a9b3..dc68fa0 100644
> --- a/net/can/raw.c
> +++ b/net/can/raw.c
> @@ -82,6 +82,8 @@ struct raw_sock {
>  	int loopback;
>  	int recv_own_msgs;
>  	int fd_frames;
> +	int join_filters;
> +	int __percpu *join_rx_count;
>  	int count;                 /* number of active filters */
>  	struct can_filter dfilter; /* default/single filter */
>  	struct can_filter *filter; /* pointer to filter(s) */
> @@ -128,10 +130,20 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
>  	/* eliminate multiple filter matches for the same skb */
>  	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>  	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
> +		if (ro->join_filters) {
> +			this_cpu_inc(*ro->join_rx_count);
> +			/* drop frame until all enabled filters matched */
> +			if (*this_cpu_ptr(ro->join_rx_count) < ro->count)

Can we be sure, that all skbs are processed on the same CPU? So that
it's sufficient to just compare the "ro->join_rx_count" of this CPU with
"ro->count" (or do we have to use join_rx_count of all CPUs?)

> +				return;
> +		} else
>  			return;

nitpick: please use { } on both sides of the else.

>  	} else {
>  		*this_cpu_ptr(ro->uniq_skb) = oskb;
>  		*this_cpu_ptr(ro->uniq_tstamp) = oskb->tstamp;
> +		*this_cpu_ptr(ro->join_rx_count) = 1;
> +		/* drop first frame to check all enabled filters? */
> +		if (ro->join_filters && ro->count > 1)
> +			return;
>  	}

Marc

-- 
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH RFC v2 1/2] can: fix multiple delivery of a single CAN frame for overlapping CAN filters

[Oliver Hartkopp]

On 31.03.2015 14:32, Marc Kleine-Budde wrote:
> On 03/30/2015 12:41 PM, Oliver Hartkopp wrote:
>> Please check out
>>
>> https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
>>
>> And especially
>> https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/x173.html#LOCK-SOFTIRQS-SAME
>>
>> When a softirq processes an incoming skb this remains on that selected CPU.
>
> Okay, I was not sure about this. What about preempt_rt?
>

I don't care :-)

There are so many implementations that rely on this per-CPU stuff that we can 
assume preempt_rt takes care of it (e.g. with locking or reducing CPU cores, etc)

>> Putting a struct into these percpu handling can be done - but does it increase
>> the readability in this case?
>
> It saves ressources, 1 pointer instead of 3 (considering both of your
> patches) and only 1 allocation.

Yes. I did some more code reading, created a struct for it and omitted the 
initialization as alloc_percpu returns an already zero'ed memory region.

Will send tomorrow morning.

Regards,
Oliver

Re: [PATCH RFC v2 2/2] can: introduce new raw socket option to join the given CAN filters

[Oliver Hartkopp]

On 31.03.2015 14:36, Marc Kleine-Budde wrote:
> On 03/29/2015 08:09 PM, Oliver Hartkopp wrote:


>> @@ -128,10 +130,20 @@ static void raw_rcv(struct sk_buff *oskb, void *data)
>>   	/* eliminate multiple filter matches for the same skb */
>>   	if (*this_cpu_ptr(ro->uniq_skb) == oskb &&
>>   	    ktime_equal(*this_cpu_ptr(ro->uniq_tstamp), oskb->tstamp)) {
>> +		if (ro->join_filters) {
>> +			this_cpu_inc(*ro->join_rx_count);
>> +			/* drop frame until all enabled filters matched */
>> +			if (*this_cpu_ptr(ro->join_rx_count) < ro->count)
>
> Can we be sure, that all skbs are processed on the same CPU? So that
> it's sufficient to just compare the "ro->join_rx_count" of this CPU with
> "ro->count" (or do we have to use join_rx_count of all CPUs?)
>

No, that's exactly the point that the single CAN frame skb is processed inside 
the softirq by one CPU. And we count only for this specific skb here.

The next frame which is processed in raw_rcv() might use another CPU while 
executing the NET_RX softirq.

>> +				return;
>> +		} else
>>   			return;
>
> nitpick: please use { } on both sides of the else.
>

fixed in v3

Regards,
Oliver