[PATCH 0/3] can: add support for hash based access to EFF frame filters

[PATCH 0/3] can: add support for hash based access to EFF frame filters

[Oliver Hartkopp]

In contrast to the direct access to the single SFF frame filters (which are
indexed by the SFF CAN ID itself) the single EFF frame filters are arranged
in a single linked hlist. To reduce the hlist traversal in the case of many
filter subscriptions a hash based access is introduced for single EFF filters.

This patch set enhances and documents the hash based EFF filter sets in
af_can.c .

Oliver Hartkopp (3):
  can: proc: make array printing function indenpendent from sff frames
  can: add hash based access to single EFF frame filters
  can: add documentation for CAN filter usage optimisation

 Documentation/networking/can.txt | 35 ++++++++++++++++++
 net/can/af_can.c                 | 31 +++++++++++++---
 net/can/af_can.h                 |  9 +++--
 net/can/proc.c                   | 76 ++++++++++++++++++++++++++++++++--------
 4 files changed, 129 insertions(+), 22 deletions(-)

-- 
1.9.1

[PATCH 1/3] can: proc: make array printing function indenpendent from sff frames

[Oliver Hartkopp]

The can_rcvlist_sff_proc_show_one() function which prints the array of filters
for the single SFF CAN identifiers is prepared to be used by a second caller.
Therefore it is also renamed to properly describe its future functionality.

Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
---
 net/can/af_can.h |  4 +++-
 net/can/proc.c   | 28 ++++++++++++++++------------
 2 files changed, 19 insertions(+), 13 deletions(-)

diff --git a/net/can/af_can.h b/net/can/af_can.h
index 6de58b4..989e695 100644
--- a/net/can/af_can.h
+++ b/net/can/af_can.h
@@ -59,12 +59,14 @@ struct receiver {
 	char *ident;
 };
 
+#define CAN_SFF_RCV_ARRAY_SZ (1<<CAN_SFF_ID_BITS)
+
 enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
 
 /* per device receive filters linked at dev->ml_priv */
 struct dev_rcv_lists {
 	struct hlist_head rx[RX_MAX];
-	struct hlist_head rx_sff[0x800];
+	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
 	int remove_on_zero_entries;
 	int entries;
 };
diff --git a/net/can/proc.c b/net/can/proc.c
index b543470..1f8e1e6 100644
--- a/net/can/proc.c
+++ b/net/can/proc.c
@@ -389,25 +389,26 @@ static const struct file_operations can_rcvlist_proc_fops = {
 	.release	= single_release,
 };
 
-static inline void can_rcvlist_sff_proc_show_one(struct seq_file *m,
-						 struct net_device *dev,
-						 struct dev_rcv_lists *d)
+static inline void can_rcvlist_proc_show_array(struct seq_file *m,
+					       struct net_device *dev,
+					       struct hlist_head *rcv_array,
+					       unsigned int rcv_array_sz)
 {
-	int i;
+	unsigned int i;
 	int all_empty = 1;
 
 	/* check whether at least one list is non-empty */
-	for (i = 0; i < 0x800; i++)
-		if (!hlist_empty(&d->rx_sff[i])) {
+	for (i = 0; i < rcv_array_sz; i++)
+		if (!hlist_empty(&rcv_array[i])) {
 			all_empty = 0;
 			break;
 		}
 
 	if (!all_empty) {
 		can_print_recv_banner(m);
-		for (i = 0; i < 0x800; i++) {
-			if (!hlist_empty(&d->rx_sff[i]))
-				can_print_rcvlist(m, &d->rx_sff[i], dev);
+		for (i = 0; i < rcv_array_sz; i++) {
+			if (!hlist_empty(&rcv_array[i]))
+				can_print_rcvlist(m, &rcv_array[i], dev);
 		}
 	} else
 		seq_printf(m, "  (%s: no entry)\n", DNAME(dev));
@@ -425,12 +426,15 @@ static int can_rcvlist_sff_proc_show(struct seq_file *m, void *v)
 
 	/* sff receive list for 'all' CAN devices (dev == NULL) */
 	d = &can_rx_alldev_list;
-	can_rcvlist_sff_proc_show_one(m, NULL, d);
+	can_rcvlist_proc_show_array(m, NULL, d->rx_sff, CAN_SFF_RCV_ARRAY_SZ);
 
 	/* sff receive list for registered CAN devices */
 	for_each_netdev_rcu(&init_net, dev) {
-		if (dev->type == ARPHRD_CAN && dev->ml_priv)
-			can_rcvlist_sff_proc_show_one(m, dev, dev->ml_priv);
+		if (dev->type == ARPHRD_CAN && dev->ml_priv) {
+			d = dev->ml_priv;
+			can_rcvlist_proc_show_array(m, dev, d->rx_sff,
+						    CAN_SFF_RCV_ARRAY_SZ);
+		}
 	}
 
 	rcu_read_unlock();
-- 
1.9.1

Re: [PATCH 1/3] can: proc: make array printing function indenpendent from sff frames

[Marc Kleine-Budde]

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

On 04/01/2014 08:57 PM, Oliver Hartkopp wrote:
> The can_rcvlist_sff_proc_show_one() function which prints the array of filters
> for the single SFF CAN identifiers is prepared to be used by a second caller.
> Therefore it is also renamed to properly describe its future functionality.
> 
> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>

Looks good, some nitpicks inline.

> ---
>  net/can/af_can.h |  4 +++-
>  net/can/proc.c   | 28 ++++++++++++++++------------
>  2 files changed, 19 insertions(+), 13 deletions(-)
> 
> diff --git a/net/can/af_can.h b/net/can/af_can.h
> index 6de58b4..989e695 100644
> --- a/net/can/af_can.h
> +++ b/net/can/af_can.h
> @@ -59,12 +59,14 @@ struct receiver {
>  	char *ident;
>  };
>  
> +#define CAN_SFF_RCV_ARRAY_SZ (1<<CAN_SFF_ID_BITS)

Please add spaces around the <<

> +
>  enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
>  
>  /* per device receive filters linked at dev->ml_priv */
>  struct dev_rcv_lists {
>  	struct hlist_head rx[RX_MAX];
> -	struct hlist_head rx_sff[0x800];
> +	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
>  	int remove_on_zero_entries;
>  	int entries;
>  };
> diff --git a/net/can/proc.c b/net/can/proc.c
> index b543470..1f8e1e6 100644
> --- a/net/can/proc.c
> +++ b/net/can/proc.c
> @@ -389,25 +389,26 @@ static const struct file_operations can_rcvlist_proc_fops = {
>  	.release	= single_release,
>  };
>  
> -static inline void can_rcvlist_sff_proc_show_one(struct seq_file *m,
> -						 struct net_device *dev,
> -						 struct dev_rcv_lists *d)
> +static inline void can_rcvlist_proc_show_array(struct seq_file *m,
> +					       struct net_device *dev,
> +					       struct hlist_head *rcv_array,
> +					       unsigned int rcv_array_sz)
>  {
	> -	int i;
> +	unsigned int i;
>  	int all_empty = 1;
>  
>  	/* check whether at least one list is non-empty */
> -	for (i = 0; i < 0x800; i++)
> -		if (!hlist_empty(&d->rx_sff[i])) {
> +	for (i = 0; i < rcv_array_sz; i++)
> +		if (!hlist_empty(&rcv_array[i])) {
>  			all_empty = 0;
>  			break;
>  		}
>  
>  	if (!all_empty) {
>  		can_print_recv_banner(m);
> -		for (i = 0; i < 0x800; i++) {
> -			if (!hlist_empty(&d->rx_sff[i]))
> -				can_print_rcvlist(m, &d->rx_sff[i], dev);
> +		for (i = 0; i < rcv_array_sz; i++) {
> +			if (!hlist_empty(&rcv_array[i]))
> +				can_print_rcvlist(m, &rcv_array[i], dev);
>  		}
>  	} else
>  		seq_printf(m, "  (%s: no entry)\n", DNAME(dev));
> @@ -425,12 +426,15 @@ static int can_rcvlist_sff_proc_show(struct seq_file *m, void *v)
>  
>  	/* sff receive list for 'all' CAN devices (dev == NULL) */
>  	d = &can_rx_alldev_list;
> -	can_rcvlist_sff_proc_show_one(m, NULL, d);
> +	can_rcvlist_proc_show_array(m, NULL, d->rx_sff, CAN_SFF_RCV_ARRAY_SZ);

Please use ARRAY_SIZE(d->rx_sff)

>  
>  	/* sff receive list for registered CAN devices */
>  	for_each_netdev_rcu(&init_net, dev) {
> -		if (dev->type == ARPHRD_CAN && dev->ml_priv)
> -			can_rcvlist_sff_proc_show_one(m, dev, dev->ml_priv);
> +		if (dev->type == ARPHRD_CAN && dev->ml_priv) {
> +			d = dev->ml_priv;
> +			can_rcvlist_proc_show_array(m, dev, d->rx_sff,
> +						    CAN_SFF_RCV_ARRAY_SZ);
Please use ARRAY_SIZE(d->rx_sff)
> +		}
>  	}
>  
>  	rcu_read_unlock();
> 
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: 242 bytes --]

[PATCH 2/3] can: add hash based access to single EFF frame filters

[Oliver Hartkopp]

In contrast to the direct access to the single SFF frame filters (which are
indexed by the SFF CAN ID itself) the single EFF frame filters are arranged
in a single linked hlist. To reduce the hlist traversal in the case of many
filter subscriptions a hash based access is introduced for single EFF filters.

Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
---
 net/can/af_can.c | 31 ++++++++++++++++++++++++++-----
 net/can/af_can.h |  5 ++++-
 net/can/proc.c   | 48 +++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 75 insertions(+), 9 deletions(-)

diff --git a/net/can/af_can.c b/net/can/af_can.c
index a27f8aa..56fd1e2 100644
--- a/net/can/af_can.c
+++ b/net/can/af_can.c
@@ -338,6 +338,29 @@ static struct dev_rcv_lists *find_dev_rcv_lists(struct net_device *dev)
 }
 
 /**
+ * effhash - hash function for 29 bit CAN identifier reduction
+ * @can_id: 29 bit CAN identifier
+ *
+ * Description:
+ *  To reduce the linear traversal in one linked list of _single_ EFF CAN
+ *  frame subscriptions the 29 bit identifier is mapped to 10 bits.
+ *  (see CAN_EFF_RCV_HASH_BITS definition)
+ *
+ * Return:
+ *  Hash value from 0x000 - 0x3FF ( enforced by CAN_EFF_RCV_HASH_BITS mask )
+ */
+static unsigned int effhash(canid_t can_id)
+{
+	unsigned int hash;
+
+	hash = can_id>>(2*CAN_EFF_RCV_HASH_BITS);
+	hash ^= can_id>>CAN_EFF_RCV_HASH_BITS;
+	hash ^= can_id;
+
+	return hash & ((1<<CAN_EFF_RCV_HASH_BITS) - 1);
+}
+
+/**
  * find_rcv_list - determine optimal filterlist inside device filter struct
  * @can_id: pointer to CAN identifier of a given can_filter
  * @mask: pointer to CAN mask of a given can_filter
@@ -400,10 +423,8 @@ static struct hlist_head *find_rcv_list(canid_t *can_id, canid_t *mask,
 	    !(*can_id & CAN_RTR_FLAG)) {
 
 		if (*can_id & CAN_EFF_FLAG) {
-			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS)) {
-				/* RFC: a future use-case for hash-tables? */
-				return &d->rx[RX_EFF];
-			}
+			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS))
+				return &d->rx_eff[effhash(*can_id)];
 		} else {
 			if (*mask == (CAN_SFF_MASK | CAN_EFF_RTR_FLAGS))
 				return &d->rx_sff[*can_id];
@@ -632,7 +653,7 @@ static int can_rcv_filter(struct dev_rcv_lists *d, struct sk_buff *skb)
 		return matches;
 
 	if (can_id & CAN_EFF_FLAG) {
-		hlist_for_each_entry_rcu(r, &d->rx[RX_EFF], list) {
+		hlist_for_each_entry_rcu(r, &d->rx_eff[effhash(can_id)], list) {
 			if (r->can_id == can_id) {
 				deliver(skb, r);
 				matches++;
diff --git a/net/can/af_can.h b/net/can/af_can.h
index 989e695..5796bc9 100644
--- a/net/can/af_can.h
+++ b/net/can/af_can.h
@@ -60,13 +60,16 @@ struct receiver {
 };
 
 #define CAN_SFF_RCV_ARRAY_SZ (1<<CAN_SFF_ID_BITS)
+#define CAN_EFF_RCV_HASH_BITS 10
+#define CAN_EFF_RCV_ARRAY_SZ (1<<CAN_EFF_RCV_HASH_BITS)
 
-enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
+enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_MAX };
 
 /* per device receive filters linked at dev->ml_priv */
 struct dev_rcv_lists {
 	struct hlist_head rx[RX_MAX];
 	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
+	struct hlist_head rx_eff[CAN_EFF_RCV_ARRAY_SZ];
 	int remove_on_zero_entries;
 	int entries;
 };
diff --git a/net/can/proc.c b/net/can/proc.c
index 1f8e1e6..e26499d 100644
--- a/net/can/proc.c
+++ b/net/can/proc.c
@@ -80,7 +80,6 @@ static const char rx_list_name[][8] = {
 	[RX_ALL] = "rx_all",
 	[RX_FIL] = "rx_fil",
 	[RX_INV] = "rx_inv",
-	[RX_EFF] = "rx_eff",
 };
 
 /*
@@ -456,6 +455,49 @@ static const struct file_operations can_rcvlist_sff_proc_fops = {
 	.release	= single_release,
 };
 
+
+static int can_rcvlist_eff_proc_show(struct seq_file *m, void *v)
+{
+	struct net_device *dev;
+	struct dev_rcv_lists *d;
+
+	/* RX_EFF */
+	seq_puts(m, "\nreceive list 'rx_eff':\n");
+
+	rcu_read_lock();
+
+	/* eff receive list for 'all' CAN devices (dev == NULL) */
+	d = &can_rx_alldev_list;
+	can_rcvlist_proc_show_array(m, NULL, d->rx_eff, CAN_EFF_RCV_ARRAY_SZ);
+
+	/* eff receive list for registered CAN devices */
+	for_each_netdev_rcu(&init_net, dev) {
+		if (dev->type == ARPHRD_CAN && dev->ml_priv) {
+			d = dev->ml_priv;
+			can_rcvlist_proc_show_array(m, dev, d->rx_eff,
+						    CAN_EFF_RCV_ARRAY_SZ);
+		}
+	}
+
+	rcu_read_unlock();
+
+	seq_putc(m, '\n');
+	return 0;
+}
+
+static int can_rcvlist_eff_proc_open(struct inode *inode, struct file *file)
+{
+	return single_open(file, can_rcvlist_eff_proc_show, NULL);
+}
+
+static const struct file_operations can_rcvlist_eff_proc_fops = {
+	.owner		= THIS_MODULE,
+	.open		= can_rcvlist_eff_proc_open,
+	.read		= seq_read,
+	.llseek		= seq_lseek,
+	.release	= single_release,
+};
+
 /*
  * proc utility functions
  */
@@ -495,8 +537,8 @@ void can_init_proc(void)
 					   &can_rcvlist_proc_fops, (void *)RX_FIL);
 	pde_rcvlist_inv = proc_create_data(CAN_PROC_RCVLIST_INV, 0644, can_dir,
 					   &can_rcvlist_proc_fops, (void *)RX_INV);
-	pde_rcvlist_eff = proc_create_data(CAN_PROC_RCVLIST_EFF, 0644, can_dir,
-					   &can_rcvlist_proc_fops, (void *)RX_EFF);
+	pde_rcvlist_eff = proc_create(CAN_PROC_RCVLIST_EFF, 0644, can_dir,
+				      &can_rcvlist_eff_proc_fops);
 	pde_rcvlist_sff = proc_create(CAN_PROC_RCVLIST_SFF, 0644, can_dir,
 				      &can_rcvlist_sff_proc_fops);
 }
-- 
1.9.1

Re: [PATCH 2/3] can: add hash based access to single EFF frame filters

[Marc Kleine-Budde]

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

On 04/01/2014 08:57 PM, Oliver Hartkopp wrote:
> In contrast to the direct access to the single SFF frame filters (which are
> indexed by the SFF CAN ID itself) the single EFF frame filters are arranged
> in a single linked hlist. To reduce the hlist traversal in the case of many
> filter subscriptions a hash based access is introduced for single EFF filters.
> 
> Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>

Looks good, some comments on style inline.

> ---
>  net/can/af_can.c | 31 ++++++++++++++++++++++++++-----
>  net/can/af_can.h |  5 ++++-
>  net/can/proc.c   | 48 +++++++++++++++++++++++++++++++++++++++++++++---
>  3 files changed, 75 insertions(+), 9 deletions(-)
> 
> diff --git a/net/can/af_can.c b/net/can/af_can.c
> index a27f8aa..56fd1e2 100644
> --- a/net/can/af_can.c
> +++ b/net/can/af_can.c
> @@ -338,6 +338,29 @@ static struct dev_rcv_lists *find_dev_rcv_lists(struct net_device *dev)
>  }
>  
>  /**
> + * effhash - hash function for 29 bit CAN identifier reduction
> + * @can_id: 29 bit CAN identifier
> + *
> + * Description:
> + *  To reduce the linear traversal in one linked list of _single_ EFF CAN
> + *  frame subscriptions the 29 bit identifier is mapped to 10 bits.
> + *  (see CAN_EFF_RCV_HASH_BITS definition)
> + *
> + * Return:
> + *  Hash value from 0x000 - 0x3FF ( enforced by CAN_EFF_RCV_HASH_BITS mask )
> + */
> +static unsigned int effhash(canid_t can_id)
> +{
> +	unsigned int hash;
> +
> +	hash = can_id>>(2*CAN_EFF_RCV_HASH_BITS);
> +	hash ^= can_id>>CAN_EFF_RCV_HASH_BITS;

Please add spaces around the >> and the * operator.

> +	hash ^= can_id;
> +
> +	return hash & ((1<<CAN_EFF_RCV_HASH_BITS) - 1);
> +}

Poking the compilers with a stick I found out that...[1]

> +
> +/**
>   * find_rcv_list - determine optimal filterlist inside device filter struct
>   * @can_id: pointer to CAN identifier of a given can_filter
>   * @mask: pointer to CAN mask of a given can_filter
> @@ -400,10 +423,8 @@ static struct hlist_head *find_rcv_list(canid_t *can_id, canid_t *mask,
>  	    !(*can_id & CAN_RTR_FLAG)) {
>  
>  		if (*can_id & CAN_EFF_FLAG) {
> -			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS)) {
> -				/* RFC: a future use-case for hash-tables? */
> -				return &d->rx[RX_EFF];
> -			}
> +			if (*mask == (CAN_EFF_MASK | CAN_EFF_RTR_FLAGS))
> +				return &d->rx_eff[effhash(*can_id)];
>  		} else {
>  			if (*mask == (CAN_SFF_MASK | CAN_EFF_RTR_FLAGS))
>  				return &d->rx_sff[*can_id];
> @@ -632,7 +653,7 @@ static int can_rcv_filter(struct dev_rcv_lists *d, struct sk_buff *skb)
>  		return matches;
>  
>  	if (can_id & CAN_EFF_FLAG) {
> -		hlist_for_each_entry_rcu(r, &d->rx[RX_EFF], list) {
> +		hlist_for_each_entry_rcu(r, &d->rx_eff[effhash(can_id)], list) {
>  			if (r->can_id == can_id) {
>  				deliver(skb, r);
>  				matches++;
> diff --git a/net/can/af_can.h b/net/can/af_can.h
> index 989e695..5796bc9 100644
> --- a/net/can/af_can.h
> +++ b/net/can/af_can.h
> @@ -60,13 +60,16 @@ struct receiver {
>  };
>  
>  #define CAN_SFF_RCV_ARRAY_SZ (1<<CAN_SFF_ID_BITS)
> +#define CAN_EFF_RCV_HASH_BITS 10
> +#define CAN_EFF_RCV_ARRAY_SZ (1<<CAN_EFF_RCV_HASH_BITS)

Please add spaces around the <<.

>  
> -enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_EFF, RX_MAX };
> +enum { RX_ERR, RX_ALL, RX_FIL, RX_INV, RX_MAX };
>  
>  /* per device receive filters linked at dev->ml_priv */
>  struct dev_rcv_lists {
>  	struct hlist_head rx[RX_MAX];
>  	struct hlist_head rx_sff[CAN_SFF_RCV_ARRAY_SZ];
> +	struct hlist_head rx_eff[CAN_EFF_RCV_ARRAY_SZ];
>  	int remove_on_zero_entries;
>  	int entries;
>  };
> diff --git a/net/can/proc.c b/net/can/proc.c
> index 1f8e1e6..e26499d 100644
> --- a/net/can/proc.c
> +++ b/net/can/proc.c
> @@ -80,7 +80,6 @@ static const char rx_list_name[][8] = {
>  	[RX_ALL] = "rx_all",
>  	[RX_FIL] = "rx_fil",
>  	[RX_INV] = "rx_inv",
> -	[RX_EFF] = "rx_eff",
>  };
>  
>  /*
> @@ -456,6 +455,49 @@ static const struct file_operations can_rcvlist_sff_proc_fops = {
>  	.release	= single_release,
>  };
>  
> +
> +static int can_rcvlist_eff_proc_show(struct seq_file *m, void *v)
> +{
> +	struct net_device *dev;
> +	struct dev_rcv_lists *d;
> +
> +	/* RX_EFF */
> +	seq_puts(m, "\nreceive list 'rx_eff':\n");
> +
> +	rcu_read_lock();
> +
> +	/* eff receive list for 'all' CAN devices (dev == NULL) */
> +	d = &can_rx_alldev_list;
> +	can_rcvlist_proc_show_array(m, NULL, d->rx_eff, CAN_EFF_RCV_ARRAY_SZ);
> +
> +	/* eff receive list for registered CAN devices */
> +	for_each_netdev_rcu(&init_net, dev) {
> +		if (dev->type == ARPHRD_CAN && dev->ml_priv) {
> +			d = dev->ml_priv;
> +			can_rcvlist_proc_show_array(m, dev, d->rx_eff,
> +						    CAN_EFF_RCV_ARRAY_SZ);
> +		}
> +	}
> +
> +	rcu_read_unlock();
> +
> +	seq_putc(m, '\n');
> +	return 0;
> +}
> +
> +static int can_rcvlist_eff_proc_open(struct inode *inode, struct file *file)
> +{
> +	return single_open(file, can_rcvlist_eff_proc_show, NULL);
> +}
> +
> +static const struct file_operations can_rcvlist_eff_proc_fops = {
> +	.owner		= THIS_MODULE,
> +	.open		= can_rcvlist_eff_proc_open,
> +	.read		= seq_read,
> +	.llseek		= seq_lseek,
> +	.release	= single_release,
> +};
> +
>  /*
>   * proc utility functions
>   */
> @@ -495,8 +537,8 @@ void can_init_proc(void)
>  					   &can_rcvlist_proc_fops, (void *)RX_FIL);
>  	pde_rcvlist_inv = proc_create_data(CAN_PROC_RCVLIST_INV, 0644, can_dir,
>  					   &can_rcvlist_proc_fops, (void *)RX_INV);
> -	pde_rcvlist_eff = proc_create_data(CAN_PROC_RCVLIST_EFF, 0644, can_dir,
> -					   &can_rcvlist_proc_fops, (void *)RX_EFF);
> +	pde_rcvlist_eff = proc_create(CAN_PROC_RCVLIST_EFF, 0644, can_dir,
> +				      &can_rcvlist_eff_proc_fops);
>  	pde_rcvlist_sff = proc_create(CAN_PROC_RCVLIST_SFF, 0644, can_dir,
>  				      &can_rcvlist_sff_proc_fops);
>  }
> 

Marc

[1] After a long long long search I found a compiler (Debian clang
version 3.4-2 (tags/RELEASE_34/final) (based on LLVM 3.4) in 32 Bit
mode) that produces a function with more more instruction for your
"backwards" hash compared to a "forward" hash:

	hash = can_id;
	hash ^= can_id >> CAN_EFF_RCV_HASH_BITS;
	hash ^= can_id >> (2 * CAN_EFF_RCV_HASH_BITS);

	return hash & ((1 << CAN_EFF_RCV_HASH_BITS) - 1);

In 64 bit mode it issues the same number of instructions, though your
backwards hash is a byte shorter :) gcc 4.7 in contrast creates same
number of instructions and bytes for 32 and 64 bit.

-- 
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: 242 bytes --]

Re: [PATCH 2/3] can: add hash based access to single EFF frame filters

[Oliver Hartkopp]

On 02.04.2014 12:06, Marc Kleine-Budde wrote:

> 
> [1] After a long long long search I found a compiler (Debian clang
> version 3.4-2 (tags/RELEASE_34/final) (based on LLVM 3.4) in 32 Bit
> mode) that produces a function with more more instruction for your
> "backwards" hash compared to a "forward" hash:
> 
> 	hash = can_id;
> 	hash ^= can_id >> CAN_EFF_RCV_HASH_BITS;
> 	hash ^= can_id >> (2 * CAN_EFF_RCV_HASH_BITS);
> 
> 	return hash & ((1 << CAN_EFF_RCV_HASH_BITS) - 1);
> 
> In 64 bit mode it issues the same number of instructions, though your
> backwards hash is a byte shorter :) gcc 4.7 in contrast creates same
> number of instructions and bytes for 32 and 64 bit.
> 

Ok, I see you really had fun with this review :-)

Will change the hash function like this - and the other stuff too.

Thanks,
Oliver

[PATCH 3/3] can: add documentation for CAN filter usage optimisation

[Oliver Hartkopp]

To benefit from special filters for single SFF or single EFF CAN identifier
subscriptions the CAN_EFF_FLAG bit and the CAN_RTR_FLAG bit has to be set
together with the CAN_(SFF|EFF)_MASK in can_filter.mask.

Signed-off-by: Oliver Hartkopp <socketcan@hartkopp.net>
---
 Documentation/networking/can.txt | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/Documentation/networking/can.txt b/Documentation/networking/can.txt
index 0cbe6ec..9261fe8 100644
--- a/Documentation/networking/can.txt
+++ b/Documentation/networking/can.txt
@@ -469,6 +469,41 @@ solution for a couple of reasons:
   having this 'send only' use-case we may remove the receive list in the
   Kernel to save a little (really a very little!) CPU usage.
 
+  4.1.1.1 CAN filter usage optimisation
+
+  The CAN filters are processed in per-device filter lists at CAN frame
+  reception time. To reduce the number of checks that need to be performed
+  while walking through the filter lists the CAN core provides an optimized
+  filter handling when the filter subscription focusses on a single CAN ID.
+
+  For the possible 2048 SFF CAN identifiers the identifier is used as an index
+  to access the corresponding subscription list without any further checks.
+  For the 2^29 possible EFF CAN identifiers a 10 bit XOR folding is used as
+  hash function to retrieve the EFF table index.
+
+  To benefit from the optimized filters for single CAN identifiers the
+  CAN_SFF_MASK or CAN_EFF_MASK have to be set into can_filter.mask together
+  with set CAN_EFF_FLAG and CAN_RTR_FLAG bits. A set CAN_EFF_FLAG bit in the
+  can_filter.mask makes clear that it matters whether a SFF or EFF CAN ID is
+  subscribed. E.g. in the example from above
+
+    rfilter[0].can_id   = 0x123;
+    rfilter[0].can_mask = CAN_SFF_MASK;
+
+  both SFF frames with CAN ID 0x123 and EFF frames with 0xXXXXX123 can pass.
+
+  To filter for only 0x123 (SFF) and 0x12345678 (EFF) CAN identifiers the
+  filter has to be defined in this way to benefit from the optimized filters:
+
+    struct can_filter rfilter[2];
+
+    rfilter[0].can_id   = 0x123;
+    rfilter[0].can_mask = (CAN_EFF_FLAG | CAN_RTR_FLAG | CAN_SFF_MASK);
+    rfilter[1].can_id   = 0x12345678 | CAN_EFF_FLAG;
+    rfilter[1].can_mask = (CAN_EFF_FLAG | CAN_RTR_FLAG | CAN_EFF_MASK);
+
+    setsockopt(s, SOL_CAN_RAW, CAN_RAW_FILTER, &rfilter, sizeof(rfilter));
+
   4.1.2 RAW socket option CAN_RAW_ERR_FILTER
 
   As described in chapter 3.4 the CAN interface driver can generate so
-- 
1.9.1